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

求大神解答下..一直WA。C++

Posted by 221200107 at 2014-09-10 23:47:23 on Problem 2392
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int dp[402][12];//定义dp[i][j]表示前i种物品,第i种挑j个的最大值
struct wood
{
	int hi;
	int maxh;
	int count;
};
int n;
wood wss[402];
bool cmp(wood a,wood b)
{
	if(a.maxh<b.maxh)
		return true;
	else 
	{
		if(a.maxh==b.maxh&&a.hi<b.hi)
			return true;
		else
			return false;
	}
		
}
int max(int a,int b)
{
	return a>b? a:b;
}
void solve()
{
	memset(dp,-1,sizeof(dp));
	sort(wss,wss+n,cmp);
	dp[1][0]=0;
	for(int i=1;i<=wss[0].count;i++)
	{
		if(i*wss[0].hi<=wss[0].maxh)
			dp[1][i]=i*wss[0].hi;
	}
	int maxx;
	for(int i1=2;i1<=n;i1++)
	{
		for(int j=0;j<=wss[i1-1].count;j++)
		{
			maxx=-2;
			for(int j2=0;j2<=wss[i1-2].count;j2++)
			{
				if(dp[i1-1][j2]!=-1)
				{
					if(dp[i1-1][j2]+wss[i1-1].hi*j<=wss[i1-1].maxh)
					{
						maxx=max(dp[i1-1][j2]+wss[i1-1].hi*j,maxx);
					}
				}
			}
			if(maxx!=-2)
				dp[i1][j]=maxx;
		}
	}
	maxx=-2;
	for(int i2=0;i2<=wss[n-1].count;i2++)
	{
		if(dp[n][i2]!=-1)
			maxx=max(maxx,dp[n][i2]);
	}
	cout<<maxx<<endl;

}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>wss[i].hi>>wss[i].maxh>>wss[i].count;
	}
	solve();
}

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