usaco: Money Systems

本文主要是介绍usaco: Money Systems，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

res(i, j)表示用前 j 种组合出 i 。那么：res(i, j) = res(i - coin[i], j - 1) + res(i, j - 1)，即结果有两种情况：取第 j 种钱和不取第 j 种钱。

/*
ID: 
LANG: C++
TASK: money
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>#define IN "money.in"
#define OUT "money.out"
#define MaxV 30
#define MaxN 10005using namespace std;int v, n;
int coin[MaxV];
long long res[MaxN][MaxV];  //res(i, j): 用前j种钱组合出ivoid solve()
{memset(res, 0, sizeof(0));int tmp = coin[0];while(tmp <= n) {res[tmp][1] = 1;tmp += coin[0];}for(int i = 1; i <= v; i++)res[0][i] = 1;for(int i = 2; i <= v; i++) {for(int j = 1; j <= n; j++) {if(j - coin[i-1] >= 0)res[j][i] = res[j-coin[i-1]][i] + res[j][i-1];elseres[j][i] = res[j][i-1];}}
}int main()
{freopen(IN, "rb", stdin);freopen(OUT, "wb", stdout);while(scanf("%d%d", &v, &n) != EOF) {for(int i = 0; i < v; i++)scanf("%d", &coin[i]);solve();printf("%lld\n", res[n][v]);}fclose(stdin);fclose(stdout);   return 0;
}

这篇关于usaco: Money Systems的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---