HDU 2546 饭卡 简单0-1背包+稍作处理

发布时间:2016-12-7 22:30:31 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 2546 饭卡 简单0-1背包+稍作处理",主要涉及到HDU 2546 饭卡 简单0-1背包+稍作处理方面的内容,对于HDU 2546 饭卡 简单0-1背包+稍作处理感兴趣的同学可以参考一下。

  中文题,题意自己看。 思路: 1.如果一开始钱少于5元,不买东西,按原值输出; 2.否则,先拿这五块钱买最贵的一份菜(输入菜的价格后用sort排序一下),然后对其它n-1个菜进行0-1背包处理   View Code #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; bool dp[1001]; int a[1001]; int main() { int i, j, n, m; while(~scanf("%d",&n)&&n) { for(i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); scanf("%d",&m); memset(dp,0,sizeof(dp)); dp[0]=1; if(m<5){printf("%d\n",m);continue;} //注意要考虑m<5的时候 m-=5; //总量减5 for(i=1;i<n;i++) { for(j=m;j>=a[i];j--) if(dp[j-a[i]])dp[j]=1; } for(i=m;i>=0;i--) if(dp[i])break; printf("%d\n",m-i+5-a[n]); } return 0; }

上一篇:velocity介绍及语法
下一篇:TCP/IP详解学习笔记(9)-TCP协议概述 .

相关文章

相关评论