2546 饭卡（01背包，挺好的）

网友投稿 488 2022-11-10

2546 饭卡（01背包，挺好的）

2546 饭卡（01背包，挺好的）

题目地址：#include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dp[1000];int a[1010];int main(){ int n; while(scanf("%d",&n) && n) { memset(dp,0,sizeof(dp)); int max1 = -1; int k; for(int i=1; i<=n; i++) { scanf("%d",&a[i]); if(a[i] > max1) { max1 = a[i]; k = i; } } int x; scanf("%d",&x); if(x < 5) { printf("%d\n",x); continue; } x -= 5; for(int i=1; i<=n; i++) { if(i == k) continue; for(int j=x; j>=a[i]; j--) { dp[j] = max(dp[j],dp[j-a[i]] + a[i]); } } printf("%d\n",x+5-dp[x]-max1); } return 0;}

错误代码：（这个会造成价值最大的有可能没有选，逻辑不对）

#include #include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dp[1060];int a[1010];int main(){ int n; while(scanf("%d",&n) && n) { memset(dp,0,sizeof(dp)); int max1 = 0; for(int i=1; i<=n; i++) { scanf("%d",&a[i]); if(a[i] > max1) max1 = a[i]; } int cost; scanf("%d",&cost); int x = cost; if(cost < 5) { printf("%d\n",cost); continue; } cost = cost - 5 + max1; for(int i=1; i<=n; i++) { for(int j=cost; j>=a[i]; j--) { dp[j] = max(dp[j],dp[j-a[i]]+a[i]); } } printf("%d\n",x-dp[cost]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：代码
上一篇:nyist 1070 诡异的电梯【Ⅰ】（比较好的DP）
下一篇:ZOJ 1985 Largest Rectangle in a Histogram
相关文章

 发表评论

暂时没有评论，来抢沙发吧~