电子科大本部食堂的饭卡有一种很诡异的设计, 即在购买之前判断余额. 如果购买一个商品之前, 卡上的剩余金额大于或等于 5 元, 就一定可以购买成功 (即使购买后卡上余额为负), 否则无法购买 (即使金额足够). 所以大家都希望尽量使卡上的余额最少.
某天, 食堂中有 n 种菜出售, 每种菜可购买一次. 已知每种菜的价格以及卡上的余额, 问最少可使卡上的余额为多少.
Input 多组数据. 对于每组数据:
第一行为正整数 n, 表示菜的数量. n<=1000.
第二行包括 n 个正整数, 表示每种菜的价格. 价格不超过 50.
第三行包括一个正整数 m, 表示卡上的余额. m<=1000.
n=0 表示数据结束.
Output 对于每组输入, 输出一行, 包含一个整数, 表示卡上可能的最小余额. Sample Input
- 1
- 50
- 5
- 10
- 1 2 3 2 1 1 2 3 2 1
- 50
- 0
- Sample Output
- -45
- 32
思路: 动态规划, 最后一次肯定是买最贵的那个菜, 之前就余额大于等于 5 的前提下, 能买多少就买多少
- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<cmath>
- #include<cstdlib>
- #include<queue>
- #include<set>
- #include<vector>
- using namespace std;
- #define INF 0x3f3f3f3f
- #define eps 1e-10
- typedef long long ll;
- const int maxn = 1e3+5;
- const int mod = 1e9 + 7;
- int gcd(int a, int b) {
- if (b == 0) return a; return gcd(b, a % b);
- }
- int main()
- {
- int n;
- while(scanf("%d",&n)&&n)
- {
- int cai[maxn]={0};
- int dp[maxn]={0};
- for(int i=0;i<n;i++)
- scanf("%d",&cai[i]);
- int sum;
- scanf("%d",&sum);
- int maxx=-1,pos;
- for(int i=0;i<n;i++)
- if(maxx<cai[i])
- {
- maxx=cai[i];
- pos=i;
- }
- cai[pos]=-1;
- if(sum<5)
- {
- cout<<sum<<endl;
- continue;
- }
- for(int i=0;i<n;i++)
- {
- if(i==pos)
- continue;
- for(int j=sum-5;j>=cai[i];j--)
- {
- dp[j]=max(dp[j],dp[j-cai[i]]+cai[i]);
- }
- }
- cout<<sum-dp[sum-5]-maxx<<endl;
- }
- }
来源: http://www.bubuko.com/infodetail-2733621.html