uva 674Coin Change(完全背包)

点击打开链接uva 674

思路: 完全背包

分析: 裸题

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 8000;

int sum , dp[MAXN];
int v[6]={0,1,5,10,25,50};

void solve(){
    memset(dp , 0 , sizeof(dp));
    dp[0] = 1;
    for(int i = 1 ; i <= 5 ; i++)
        for(int j = v[i] ; j < MAXN ; j++)
           dp[j] += dp[j-v[i]];
}

int main(){
    solve();
    while(scanf("%d", &sum) != EOF)
        printf("%d\n" , dp[sum]);
    return 0;
}