zoj 1161.cpp

acm.zju.edu.cn上1161题的代码。 此题可用动态规划也可用贪心

//zoj 1161 经典贪心

//枚举所有可以走过的湖，然后就可以“瞬间移动”,从中选出一个最优解

#include "stdio.h"
#include "string.h"

int main()
{
 int i,j,test,time,laketime[30],farestlake,lakenum,beginfish[30],nowfish[30],decrease[30],tmp,remaintime[30],max,fishtime[30];
 int countfish,maxtmp,k,marke,ans[30],cnt,timeleft;
 //freopen("G.17.dat","r",stdin);
 //freopen("out2.txt", "w", stdout);
 scanf("%d",&test);
 while(test--) 
 {
  cnt=0;
  while(scanf("%d",&lakenum))
 {
  if(lakenum==0) break;
  if(cnt++) printf("\n");
  scanf("%d",&time);
  time*=12;
  max=-1;
  for(i=1;i<=lakenum;i++)
  scanf("%d",&beginfish[i]);
  for(i=1;i<=lakenum;i++)
  scanf("%d",&decrease[i]);
  for(i=1;i<lakenum;i++)
  scanf("%d",&laketime[i]);
  laketime[0]=0;

  //求出能到达的最远的湖,并完成remaintime[]
  for(i=1,tmp=time,remaintime[0]=time;i<=lakenum;i++)
  {
	  tmp-=laketime[i];
	  remaintime[i]=remaintime[i-1]-laketime[i-1];
	  farestlake=i;
	  if(tmp<0) break;
  }
  
 
  //枚举走过的湖的个数
  for(i=1;i<=farestlake;i++)
  {
    memcpy(nowfish,beginfish,sizeof(nowfish));
	memset(fishtime,0,sizeof(fishtime));
    countfish=0;
	for(j=1;j<=remaintime[i];j++)
	{
		for(k=1,maxtmp=-1,marke=0;k<=i;k++)
		{
			 //当nowfish[k]与nowfish[k+1]相等时，会选k
	       if(nowfish[k]>maxtmp) {marke=k;maxtmp=nowfish[marke];} 
		   

		  
		}
		{nowfish[marke]-=decrease[marke];if(nowfish[marke]<0) nowfish[marke]=0;}
		if(maxtmp>0) {fishtime[marke]++;countfish+=maxtmp;}  //当max相等时，也会选择走过湖少的那个
		else break;
	}

	//计算timeleft
	timeleft=remaintime[i]-j+1;
	fishtime[1]+=timeleft;

	if(countfish > max)
	{
		max=countfish;
		memcpy(ans,fishtime,sizeof(ans));
	}
  }
   

  //输出
 for(i=1;i<lakenum;i++)
	 printf("%d, ",ans[i]*5);
  printf("%d\n",ans[lakenum]*5);
  printf("Number of fish expected: %d\n",max);
  }
   if(test) printf("\n");
 }

 return 0;
}