POJ 1042 Gone Fishing( DP )

题意：小明打算做一个h（(1 <= h <= 16)）个小时钓鱼旅行。发现这里有n(2 <=
n <= 25)个湖，而且所有的湖都在一条路的旁边。小明打算从第1个湖开始钓起，每在一个湖钓完鱼后，要到下一个湖但他可以选择是否要在这里钓鱼，并且他可以在任何一个湖结束他此次钓鱼的行程。输入给出小明在每个湖中单位时间内（5分钟）钓的鱼数fi[i]，以及随单位时间的增长而线性递减di[i]。没到下一个湖所需的时间为ti[i](单位时间)。求怎么样选择钓鱼的湖使得小明钓到最多的鱼，以及在每个湖钓鱼的用时。

分析：开始就想到用DP，用dp[i][j]表示前i个湖用时j个单位时间时钓到的最多鱼数。状态转换方程为：dp[i][j]=Math.max(dp[i-1][j-k-ti[i-1]]+fishs
, dp[i][j]),ti[i-1]为从第i-1个湖到第i个湖所用的时间，fishs为在k个时间单位内小明在第i个湖钓到的鱼数;但是这样求在每个湖的逗留时间有点不方便，后来发现可以再写个方法，从DP的逆过程中找到每个湖的用时。分析到这里已经可以开始写代码了，但是由于小弟的DP学的不扎实，在实现的时候还是遇到了困难。比如，dp方程是在dp[i-1][j-k-ti[i-1]]上加上fishs，这就给dp的初始化带来了麻烦。而如果是用方程dp[i][j]=Max{
dp[i-1][j-k-t[i]] , dp[i][j]+fishs }就是在dp[i][j]的基础上加上fishs，这样的初始化就很简单了。不过最初的永远是最难忘的，就像初恋一样！哎，我还是实现了我的最初想法，不过就是有点繁琐。怎么实现的呢，就是先算出不是最佳的方案，算出每个湖能钓到的鱼数，不管是不是整个过程中最多的。有点说不清楚，dp[i][j]=dp[i][j-1]+m;m就是一个单位时间内在第i个湖中钓到的鱼数。这样就完成了初始化了，在套用上面的dp就OK了。但是考虑到实用性的话，还是用另一种方案好了，简单易懂。

import java.util.Scanner;

public class Main{

	static int[] fi;

	static int[] di;

	static int[] ti;

	static int[] pi;

	static int[][] dp;

	static void path(int i, int time){

        if(i==0)

        	return;

        int summ=0;

        for(int k=0; k<=time; ++k){

            if(dp[i-1][time-k-ti[i-1]]+summ==dp[i][time]){

                pi[i]=k*5;

                path(i-1,time-k-ti[i-1]);

                return ;

            }

            if (fi[i]-k*di[i]>0)

                summ=fi[i]*(k+1)-(k+1)*k/2*di[i];

        }

        return;

    }

	 static void DP(int n,int time){

        dp[0][0]=0;

        for(int i=0; i<=n-1; i++)

            for(int j=0; j<=time; j++){

                int summ=0;

                for(int k=0; k<=time && dp[i][j]!=-1; k++){

                    if(j+k+ti[i]<=time)

                        dp[i+1][j+k+ti[i]]=Math.max(dp[i+1][j+k+ti[i]],dp[i][j]+summ);

                    else

                        break;

                    if (fi[i+1]-k*di[i+1]>0)

                       summ=fi[i+1]*(k+1)-(k+1)*k/2*di[i+1];

                }

            }

	    }  

   public static void main(String args[]){

	 Scanner sc=new Scanner(System.in);

	 int n,hours,i,j,time;

	 while(true){

		 n=sc.nextInt();

		 if(n==0){

			 break;

		 }

		 hours=sc.nextInt();

		 time=hours*12;

		 dp=new int[n+1][time+1];

		 fi=new int[n+1];

		 di=new int[n+1];

		 ti=new int[n];

		 pi=new int[n+1];

		 for(i=1;i<=n;i++)

			fi[i]=sc.nextInt();

		 for(i=1;i<=n;i++)

			di[i]=sc.nextInt();

		 for(i=1;i<n;i++){

			ti[i]=sc.nextInt();

		 }

		 for(i=0;i<=n;i++)

			for(j=0;j<=time;j++)

			    dp[i][j]=-1;

		 DP(n,time);

		 int max=0,index=1;

		 for(i=1;i<=n;i++){

			 if(max<dp[i][time]){

		         max=dp[i][time];

		         index=i;

		     }

		 }

		 path(index,time);

		 for(i=1;i<=n-1;i++)

			System.out.print(pi[i]+", ");

		 System.out.println(pi[n]);

		 System.out.println("Number of fish expected: "+max);

		 System.out.println();

	 }

  }

}

巴特西

POJ 1042 Gone Fishing( DP )

最新文章

热门文章