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

Re:求大神帮助,这段代码为什么WA!!!!

Posted by 20192660 at 2021-05-16 01:04:08 on Problem 1276
In Reply To:求大神帮助,这段代码为什么WA!!!! Posted by:liuxing12409 at 2014-05-21 23:55:10
> #include <iostream>
> 
> int cash;            
> int N;                 //货币种数
> int num[11];           //每种货币数量数组
> int value[11];         //每种货币价值
> int f[100001];         //动态规划数组
> #define Max(a,b) (a)>(b)?(a):(b)
> 
> void ZeroOnePack(int cost, int weight)
> {
> 	for (int i = cash; i >= cost; i--)
> 	{
> 		f[i] = Max(f[i], f[i - cost] + weight);
> 	}
> }
> 
> void CompletePack(int cost, int weight)
> {
> 	for (int i = cost; i <= cash; i++)
> 	{
> 		f[i] = Max(f[i], f[i - cost] + weight);
> 	}
> }
> 
> int main(void)
> {
> 	while (std::cin >> cash >> N)
> 	{
> 		for (int i = 0; i < N; i++)
> 		{
> 			std::cin >> num[i];
> 			std::cin >> value[i];
> 		}
> 		memset(f, 0, sizeof(f));
> 		for (int i = 0; i < N; i++)
> 		{
> 			if (num[i] * value[i] > cash)
> 			{
> 				CompletePack(value[i], value[i]);
> 			}
> 			else
> 			{
> 				int k = 1;
> 				int amount = num[i];
> 				while (k < amount)
> 				{
> 					ZeroOnePack(value[i], value[i]);
> 					amount -= k;
> 					k *= 2;
> 				}
> 				ZeroOnePack(amount * value[i], amount * value[i]);
> 			}
> 		}
> 		std::cout << f[cash] << std::endl;
> 	}
> 	return 0;
> }

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