链接:点我
题意:n个物品,m元钱,每个物品最多买一次,问最多可以买几件物品,并且输出方案数。加一维表示已经买几件物品。
我这里用了一个数组dp[v][2] ,dp[v][0] 储存原本要记录的 dp ,而 dp[v][1] 则记录方案数目。记住需要初始化,把所有 dp[i][1] 都设置成1。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define max(a,b) ((a)>(b)?(a):(b)) const int maxn = 33; int main() { int t; scanf("%d", &t); while (t--) { int n, rmb, cost[maxn], dp[505][2]; int i, j; scanf("%d %d", &n, &rmb); for (i=0; i<n; i++) scanf("%d", &cost[i]); memset(dp, 0, sizeof(dp)); for (i=0; i<=rmb; i++) dp[i][1] = 1; for (i=0; i<n; i++) { for (j=rmb; j>=cost[i]; j--) { if (dp[j][0] == dp[j-cost[i]][0] + 1) dp[j][1] = dp[j-cost[i]][1] + dp[j][1]; else if (dp[j][0] < dp[j-cost[i]][0] + 1) { dp[j][0] = dp[j-cost[i]][0] + 1; dp[j][1] = dp[j-cost[i]][1]; } } } if (dp[rmb][0] != 0) printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[rmb][1], dp[rmb][0]); else printf("Sorry, you can't buy anything.\n"); } return 0; }
RANK 排名居然第一,贴出来纪念一下。。