BNU OJ 1027 金币系统

金币系统

Time Limit: 1000ms

Memory Limit: 65535KB

64-bit integer IO format: %lld Java class name: Main

YC大牛自从杭州归来，喜欢没事儿摆个地摊儿什么的的赚点零钱买装备。经过一个星期的苦苦支撑，终于裸奔了一把鹰角弓出来。-_-
他在摆摊的过程中吃了不少苦头，比如，没有零钱什么的。这样的话，有人来买东西的话他就会因为找不开钱而让价。因此他希望能得知某种面值可以用多少种方式得到，比如15块的面值，可以由2个7元面值的和1个1元面值的组成。这样他定价为1块的物品一般比较容易找零钱。
为了明确题目的意图，再举一例，现有的货币系统1、2、5、10等面值。这样18元的价格可以有18x（1元）, 9x（2元）, 8x（2元）+2x（1元）, 3x（5元）+1x（2元）+1x（1元）, 等表示方法。
你的任务就是，给定面值的硬币Vi，硬币个数无限多，求出N的价格可以有多少种表示方法。

Input

第一行为一个数字Z，表示一下有Z组测试数据。
每一组测试数据由两行组成，
第一行为两个数V，N。有V (1 <= V <= 25)种硬币，和需要表示的价格N (1 <= N <= 10,000)。
第二行V个数，空格分隔。每一个数Vi表示一种已有的硬币面值。

Output

每组测试数据有一行输出，包括一个数。表示N的价值在由Vi组成的金币系统中有p种表示法。

Sample Input

Sample Output

Hint

数据量可能会比较大，保证long long不会溢出。

Source

第七届北京师范大学程序设计竞赛热身赛第三场

Author

XsugarX

解题：dp。。。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <climits>

 #include <algorithm>

 #include <cmath>

 #define LL long long

 using namespace std;

 LL dp[],d[];

 int main(){

     int i,kase,n,v,j;

     scanf("%d",&kase);

     while(kase--){

         scanf("%d %d",&n,&v);

         for(i = ; i < n; i++)

             scanf("%lld",d+i);

         memset(dp,,sizeof(dp));

         dp[] = ;

         for(i = ; i < n; i++){

             for(j = ; j+d[i] <= v; j++){

                 dp[j+d[i]] += dp[j];

             }

         }

         printf("%lld\n",dp[v]);

     }

     return ;

 }

巴特西