http://blog.csdn.net/crazy_ac/article/details/7869411
f[i][j][k]表示前i种物品,买了j个,花了小于等于k的钱的时候的方案数
因为是小于等于k,所以初始化的时候要注意哦。
那么转移的时候第i种物品取或者不取
f[i][j][k]+=f[i-1][j][k];
f[i][j][k]+=f[i-1][j-1][k-v[i]];
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 748 Accepted Submission(s): 255
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 |
#include<iostream> #include<cstring> using
namespace std; int f[50][50][510],v[50]; int n,m,ans1,ans2; int fun() { int
i,j,k; for (i=n;i>0;i--) for (j=i;j>0;j--) for (k=m;k>=0;k--) if (f[i][j][k]) { ans1=f[i][j][k]; ans2=j; return
1; } return
0; } int
main() { int
i,j,k,t; cin>>t; while (t--) { memset (v,0, sizeof (v)); cin>>n>>m; for (i=1;i<=n;i++) cin>>v[i]; memset (f, 0, sizeof (f)); for (i = 0; i <= n; i++) for (j = 0; j <= m; j++) f[i][0][j] = 1; for (i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=m;k>=0;k--) { f[i][j][k]+=f[i-1][j][k]; if (k>=v[i]) f[i][j][k]+=f[i-1][j-1][k-v[i]]; } if (fun()) cout<< "You have " <<ans1<< " selection(s) to buy with " <<ans2<< " kind(s) of souvenirs." <<endl; else cout<< "Sorry, you can‘t buy anything." <<endl; } return
0; } |
HDU-2126 Buy the souvenirs,布布扣,bubuko.com
原文:http://www.cnblogs.com/cancangood/p/3583415.html