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

想用dp作 为什么总是超时?高手帮忙看看

Posted by sven at 2007-04-15 13:13:00 on Problem 1042
#include<stdio.h>

int d[51][301];
bool c[51][301];
int s[51][301];
int fi[51];
int di[51];
int ti[51];
int len,h;
int catchnum(int k,int lake)
{
	if(fi[lake]==0) return 0;
	if(di[lake]==0) return fi[lake]*k;
	if(fi[lake]%di[lake]==0&&k>fi[lake]/di[lake])
		return (fi[lake]+di[lake])*(fi[lake]/di[lake])/2;
	if(fi[lake]%di[lake]!=0&&k>fi[lake]/di[lake])
	return (fi[lake]+di[lake]+fi[lake]%di[lake])*(fi[lake]/di[lake])/2+fi[lake]%di[lake];
	return (fi[lake]+fi[lake]-(k-1)*di[lake])*k/2;
}
void printans(int t)
{
	for(int i=1;i<=len-1;i++)
	{
		printf("%d, ",s[i][t]*5);
		if(t==0||t-s[i][t]-ti[i]<=0)
			t=0;
		else
			t=t-s[i][t]-ti[i];
	}
	printf("%d\n",s[len][t]*5);

}
long dp(int lake,int t)
{
	if(c[lake][t]==1)
		return d[lake][t];
	else
	{
		d[lake][t]=catchnum(t,lake);
		s[lake][t]=t;
		if(t-ti[lake]>0)
		{
			for(int k=t-ti[lake]-1;k>=0;k--)
			{
				int temp=catchnum(k,lake)+dp(lake+1,t-k-ti[lake]);
				if(temp>d[lake][t])
				{	
					d[lake][t]=temp;
					s[lake][t]=k;
				}
			}
		}
	}
	c[lake][t]=1;
	return d[lake][t];
}
int main(void)
{
	scanf("%d",&len);
	while(len>0)
	{
		scanf("%d",&h);h*=12;
		for(int i=1;i<=len;i++)
			scanf("%d",&fi[i]);
		for(int i=1;i<=len;i++)
			scanf("%d",&di[i]);
		for(int i=1;i<=len-1;i++)
			scanf("%d",&ti[i]);
		for(int i=1;i<=len;i++)
			for(int j=1;j<=h;j++)
				c[i][j]=0;
		for(int i=1;i<=len;i++)
		{    
			d[i][0]=0;c[i][0]=1;
			s[i][0]=0;
		}
		for(int i=1;i<=h;i++)
		{	
			d[len][i]=catchnum(i,len);
			c[len][i]=1;
			s[len][i]=i;
		}
		int ans=dp(1,h);
		printans(h);
		printf("Number of fish expected: %d\n\n",ans);
		scanf("%d",&len);
	}
}

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