2011-06-10 19:47:37Morris
d954. E. 得分
http://zerojudge.tw/ShowProblem?problemid=d954
內容 ：
世界上有各式各樣不同的比賽，每種比賽都有著不一樣的得分規則。例如：籃球，三分球 3 分，兩分球 2 分，罰球 1 分。
對於某一個特定的得分規則而言，達成某一特定分數的方式可以有很多種。以籃球為例：要拿到 3 分，可以是三分球 3 分，或是，兩分球 2 分再加上罰球 1 分，或是，三個罰球。總共有三種方式。
現在給定得分規則，與特定得分分數。問共有幾種方式可以得到這個特定分數。
輸入說明
：
第一行有一個正整數 T ，代表接下來有幾組測試資料。
每組測資第一行有兩個整數 N 和 S。(1 ≤ N ≤ 100, 1 ≤ S ≤ I0000) N 代表有幾種得分方式，S 代表目標的特定分數。下一行有 N 個數字，代表各個得分方式所得的分數。(每種方式所得的分數為正整數且不超過 5000)
輸出說明
：
對於每一筆測試資料，輸出得分方式有幾種。答案保證不會超過 263 - 1。
範例輸入 ：
2 3 3 1 2 3 2 4 2 2
範例輸出 ：
3 3
提示
：
出處
：
/**********************************************************************************/
/* Problem: d954 "E. 得分" from 2010 NPSC 國中組決賽 */
/* Language: C */
/* Result: AC (70ms, 334KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-04 22:31:42 */
/**********************************************************************************/
#include<stdio.h>
main() {
int T, N, S, a, b;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &N, &S);
long long A[100], DP[10001] = {};
for(a = 0; a < N; a++)
scanf("%lld", &A[a]);
DP[0] = 1;
for(a = 0; a < N; a++)
for(b = A[a]; b <= S; b++)
DP[b] += DP[b-A[a]];
printf("%lld\n", DP[S]);
}
return 0;
}
下一篇：d950. A. 帕斯卡三角形