| ||||||||||
| 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