Codeforces #360 E. The Values You Can Make
传送门：http://codeforces.com/contest/688/problem/E
题目大意
有 n 枚硬币 ，要支付 k 块钱。
接下来了一行输入 n 枚硬币的面值。
现在需要用 n 枚硬币的一些支付刚好 k 块钱，求问用支付的 k 块钱的这些硬币可以组成哪些面值（Tip：支付方法可不同）
输出 可组成面值数 与 可能的面值 。
题解
DP F[i][j][l]表示用到了第 i 枚硬币，支付 j 块钱，是否可以用这些硬币组成 l 的面值。
三重循环暴力转移。
代码
|
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 |
#include<cstdio> using namespace std; const int Maxn=500+5; int n,k; int c[Maxn]; bool DP[Maxn][Maxn][Maxn]; int main(){ scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%d",&c[i]); DP[0][0][0]=true; for (int i=1;i<=n;i++) for (int j=0;j<=k;j++) for (int p=0;p<=k;p++){ bool ret=DP[i-1][j][p]; if (j-c[i]>=0){ if (DP[i-1][j-c[i]][p]) ret=true; if (p-c[i]>=0) if (DP[i-1][j-c[i]][p-c[i]]) ret=true; } DP[i][j][p]=ret; } int cnt=0; for (int i=0;i<=k;i++) if (DP[n][k][i]) cnt++; printf("%d\n",cnt); for (int i=0;i<=k;i++) if (DP[n][k][i]) printf("%d ",i); printf("\n"); return 0; } |
原文链接：Codeforces #360 E. The Values You Can Make
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!