The trouble of XiaoqianTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 848 Accepted Submission(s): 272
Problem DescriptionInputOutputSample InputSample OutputAuthor/*题意：有N种coin,给出每种coin的价值Vi,和小强拥有的个数Ci,小强去购物，要付m元，求小强和店员间交换货币时的最小个数货币，即小强付出coin个数加上店员找回coin个数。*/#include<iostream>using namespace std;#define maxn 110int v[maxn],c[maxn],dp[20010],dp2[20010];int main(){ int n,m,i,k,j,ans,cas=0; while (scanf("%d%d",&n,&m) != EOF) {if(!m&&!n) break; for (i = 1;i <= n;i++) scanf("%d",&v[i]); for (i = 1;i <= n;i++) scanf("%d",&c[i]); for(i=0;i<=20005;i++) dp[i]=0x3f7f7f7f;// dp[i]=999999999; 不知道为什么用这个就错 一直错了n边 //memset(dp,63,sizeof(dp)); 这个也行 但是为什么是63 初始化是随机的 对应为一个10位数 dp[0] = 0; for (i = 1;i <= n;i++) for (k = 1;k<=c[i];k*=2) { if (c[i] < k) k = c[i]; int S = k * v[i]; for (j = 20000;j >= S;j--) dp[j] = dp[j]<(dp[j-S] + k)?dp[j]:(dp[j-S] + k);c[i] -= k; } for(i=0;i<=20005;i++) dp2[i]=0x3f7f7f7f; //dp2[i]=99999;// memset(dp2,63,sizeof(dp2)); dp2[0] = 0; for (i = 1;i <= n;i++) for (j = v[i];j <= 20000;j++) dp2[j] = dp2[j]<(dp2[j-v[i]]+1)?dp2[j]:(dp2[j-v[i]]+1); ans =0x3f3f3f3f; for (i = m;i<=20000;i++)// for(i=20000;i>=m;i--) ans = ans<(dp[i]+dp2[i-m])?ans:(dp[i]+dp2[i-m]); if (ans == 0x3f3f3f3f) ans = -1; printf("Case %d: %d\n",++cas,ans); }return 0;}