Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1A 记录庆祝 多重背包 + 记录路径 500MS

Posted by NJUT1401140226 at 2016-07-23 11:17:55 on Problem 1787
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator