//我的DP，测试N组数据正确，但没过。。。。
//假设在第i个湖完成钓鱼，分别DP到第i个湖。求最大的钓鱼数目
#include<iostream>
using namespace std;
#define GETMAX(a,b) ((a)>(b)?(a):(b))
int main(){
	int n,h,time,fi[30],di[30],ti[30],g[30],f[1000],q[1000][30],b[30],i,j,k,maxj,maxk,max,p,sum,firstmax;
	while(1){
		cin>>n;
		if(n==0) break;
		cin>>h;
		time=h*60/5;
		for(i=1;i<=n;++i) cin>>fi[i];
		for(i=1;i<=n;++i) cin>>di[i];
		for(i=1;i<n;++i)  cin>>ti[i];
		g[1]=0;
		for(i=2;i<=n;++i) g[i]=g[i-1]+ti[i-1];
		memset(f,-1,sizeof(f));f[0]=0;
		memset(q,0,sizeof(q));
		memset(b,0,sizeof(b));
		
		max=0;maxj=0;maxk=1;firstmax=0;
		//开始DP,类似背包的方式
		for(i=1;i<=n;++i){
			for(j=time;j>=0;--j){
				p=0;sum=0;
				do{
					sum=sum+fi[i]-di[i]*(p++);
					if(j-p<0) break;
					if(f[j-p]>=0){
						if(f[j-p]+sum>f[j]){
							for(k=1;k<=n;++k) q[j][k]=q[j-p][k];
							q[j][i]=p;
						}
					    f[j]=GETMAX(f[j],f[j-p]+sum);
					}
				}while(fi[i]-di[i]*p>0);
			}
			//完成到第i个湖的DP,每个湖DP完立马统计是为了消除后面DP的影响，下面计算开始统计
			for(j=time-g[i];j>=0;--j){
				for(k=n;k>=1;--k)
					if(q[j][k]>0) break;
				if(f[j]!=-1 && k==i){
					if(max<f[j]){
						max=f[j];maxj=j;maxk=k;
						for(k=1;k<=n;++k) b[k]=q[j][k];
						break;
					}
					else if(max==f[j]){
						if(firstmax<q[j][1]+time-j-g[k]){
							firstmax=q[j][1]+time-j-g[k];
							max=f[j];maxj=j;maxk=k;
						    for(k=1;k<=n;++k) b[k]=q[j][k];
						}

					}
				}
			}
		}
	
		
			
		cout<<(b[1]+time-maxj-g[maxk])*5;
		for(i=2;i<=n;++i) cout<<", "<<b[i]*5;
		cout<<endl<<"Number of fish expected: "<<max<<endl<<endl;
	}
	return 0;
}

• 贪心 (0) Robin47 2008-12-12 21:51:20