随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    饭卡小于5元时无法刷卡,但不小于五元时可以刷到爆,k种食物,一种一次,求饭卡最少可以剩多少。    
 4 How to Do:    DP动态规划,状态转移类似0-1背包问题,先把所有物品排序,找出最贵食物max。对其他食物进行0-1背包,
 5             找出其中最接近卡中余额m-5的最大值m',则结果即为m-m'-max.
 6   */
 7 #include <iostream>
 8 #include <string.h>
 9 #include <algorithm>
10 using namespace std;
11 #define max(a,b) (a)>(b)?(a):(b)
12 int d[1002];
13 int dp[1002];
14 int main(){
15     //freopen("in.txt","r",stdin);
16     int n;
17     while (scanf("%d",&n)&&n){
18         int i,j;
19         for(i=0;i<n;i++)    scanf("%d",&d[i]);
20         sort(d,d+n);
21         int maxs=d[n-1];
22         int m;
23         scanf("%d",&m);
24         if(m>=5){//此处WA了一次,要细致啊!!
25             memset(dp,0,sizeof(dp));
26             for(i=0;i<n-1;i++){
27                 for(j=m-5;j>=d[i];j--){
28                     dp[j]=max(dp[j],dp[j-d[i]]+d[i]);
29                 }
30             }
31             printf("%d\n",m-dp[m-5]-maxs);
32         }
33         else
34             printf("%d\n",m);
35     }
36     return 0;
37 }
38 
posted on 2012-03-13 20:39 Leo.W 阅读(533) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理