题目大意： 用一张有余额为m的饭卡去打饭，有n种不同价格的菜，若饭卡余额低于5元则不能打饭，打饭后余额允许为负，求余额最低为多少
大致思路： 需要注意的是饭卡余额不能低于5元，所以需要可变范围要小于等于m-5。由于菜的顺序对过程没有影响，所以sort后将价格最大的菜单独拿出来，在n-1种菜中进行动态规划。
C++：
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn=1010;int c[maxn],dp[maxn];int main(){ int n; while(scanf("%d",&n)!=EOF){ if(n==0) break; memset(dp,0,sizeof(dp)); int i,j; for(i=0;i<n;i++) scanf("%d",&c[i]); sort(c,c+n); int cost; scanf("%d",&cost); if(cost>=5){ for(i=0;i<n-1;i++) //将c[n-1]单独拿出来 for(j=cost-5;j>=c[i];j--) dp[j]=max(dp[j],dp[j-c[i]]+c[i]); PRintf("%d/n",cost-dp[cost-5]-c[n-1]); } else printf("%d/n",cost); } return 0;}新闻热点
疑难解答
