其实这题题目这么短就是为了让你AK
TimeLimit: 1000ms MemoryLimit:65535KB
64-bit integer IO format:%lld
Problem Description
给定一个长度为v的数组A和一个数n，将n用A内的一些数字的和表示，求有几种方式。（A内的同一个数字可以用多次，并且是顺序无关的，也就是说1+2和2+1是相同的）
Input
第一行是一个t表示测试数据的组数。
每组数据的第一行是两个整数v (1 <= v <= 25)和n (1 <= n <= 10,000)，第二行是v个互不相同的数表示数组A，每个数不超过n
Output
对于每组数据，输出一个整数表示答案
SampleInput
1
3 10
1 2 5
SampleOutput
10
提示
可以表示为：
1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+2
1+1+1+1+1+1+2+2
1+1+1+1+2+2+2
1+1+2+2+2+2
2+2+2+2+2
1+1+1+1+1+5
1+1+1+2+5
1+2+2+5
5+5
共10种
数据量可能会比较大，保证long long不会溢出。本题 long long 的读写使用 %lld
【思路】
/**
- 假设dp[i]为总和为i的选择的数量
- for(int i = 1; i <= n; i ++){
- for(int j = 0; j < len; j ++){
-
if(i - arr[j] >= 0) dp[i] = dp[i] + dp[i - arr[j]]; - }
- }
- 这样的状态转移方程存在重叠方案的转移
- 怎么避免重叠方案的转移
- 下面的状态避免了状态的重叠方案
- for(int i = 0; i < len; i ++){
- for(int j = arr[i]; j <= m; j ++){
- dp[j] = dp[j] + dp[j - arr[i]];
- }
- }
- **/
附上代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/**
* 假设dp[i]为总和为i的选择的数量
* for(int i = 1; i <= n; i ++){
* for(int j = 0; j < len; j ++){
* if(i - arr[j] >= 0) dp[i] = dp[i] + dp[i - arr[j]];
* }
* }
* 这样的状态转移方程存在重叠方案的转移
* 怎么避免重叠方案的转移
* 下面的状态避免了状态的重叠方案
* for(int i = 0; i < len; i ++){
* for(int j = arr[i]; j <= m; j ++){
* dp[j] = dp[j] + dp[j - arr[i]];
* }
* }
* **/
const int MAXN = 10000 + 5;
int arr[30];
ll dp[MAXN];
int t;
int main(){
scanf("%d", &t);
while(t --){
memset(dp, 0, sizeof(dp));
memset(arr, 0, sizeof(arr));
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++){
scanf("%d", &arr[i]);
}
dp[0] = 1;
for(int i = 0; i < n; i ++){
for(int j = arr[i]; j <= m; j ++){
dp[j] = dp[j] + dp[j - arr[i]];
}
}
printf("%lld
", dp[m]);
}
return 0;
}