Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
1A 记录庆祝 多重背包 + 记录路径 500MS#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; struct coinConvert{ int number , value; // 数量 价值 int index; // 储存 单个的价值编号 } coins[100]; int pow2[30]; int dp[10002]; // 和为k 的 硬币个数 int path[10002]; // 保存路径 int v[]={1,5,10,25}; int ans[4]; int main(){ int n; pow2[0]=1; for(int i=1; i<30 ; i++) pow2[i]=pow2[i-1]*2; int coinNum; int temp; while(1){ cin>>n; coinNum = 0; memset(dp,-1,sizeof(dp)); memset(ans , 0 , sizeof(ans)); for(int i=0 ; i<4 ; i++){ //将 输入的数据 2进制 化分解 cin>>temp; int j=0; while(temp){ if(temp>pow2[j]){ temp-=pow2[j]; coins[coinNum].number=pow2[j]; coins[coinNum].value=pow2[j]*v[i]; coins[coinNum].index =i; coinNum++; j++; }else{ coins[coinNum].number = temp; coins[coinNum].value = temp*v[i]; coins[coinNum].index = i; coinNum++; break; } } } if(n==0 && coinNum == 0) return 0; dp[0]=0; for(int i=0 ; i<coinNum ; i++) for(int j=n ; j>=0 ; j--){ if(j-coins[i].value>=0 && dp[j-coins[i].value]!=-1){ dp[j]=max( dp[j] , dp[j-coins[i].value] + coins[i].number ); if(dp[j] <= dp[j-coins[i].value] + coins[i].number) // 若 第i 个 被选择 则 记录到路径当中 path[j]=i; } } if(dp[n]==-1 && n!=0){ printf("Charlie cannot buy coffee.\n"); continue; } int t=n; while(t>0){ //遍历 将 路径中的值 存放到 ans 当中 ans[ coins[ path[t] ].index ]+=coins[ path[t] ].number; t-=coins[ path[t] ].value; } printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[0],ans[1],ans[2],ans[3]); } return 0; } //320K 563MS Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator