POJ 2385 DP

题意：在苹果树下，初始在第一棵树下，告诉你在第几秒的时候，那棵树下会落下苹果，告诉最多能移动的次数，然后来回移动，求能得到的最大的苹果数目。

思路：三维DP，d[第i秒][已经移动j次][当前在(1,2)棵树下]，背包优化，DP尽可能让状态简单一点，有时候维数越大越好，以免更多的if else ；

两种状态：

dp[i][j][1] = max(dp[i - 1][j - 1][2], dp[i - 1][j][1]) + (num[i] == 1);///在第1棵树下，如果num[i]==1就+1
dp[i][j][2] = max(dp[i - 1][j - 1][1], dp[i - 1][j][2]) + (num[i] == 2);///在第2棵树下，如果num[i]==2就+1

两次都是等于max（前一秒前一次交换的非当前树的苹果 , 前一秒不交换的当前树的苹果数) + 如果是当前树下+1；

这个状态的最大值等于上一个状态（交换/不交换）能得到的最大值+（1？）；

（PS： s +=(num[i]==2) 表示如果num[i]==2就加1，也可以用为 s += (num[i]>4),如果num[i]大于4就+1）

 #include <stdio.h>

 #include <iostream>

 using namespace std;

 int num[];

 int dp[][][];

 int main()

 {

     int n, times, maxsum = -;

     scanf("%d%d", &n, &times);

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

         scanf("%d", &num[i]);

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

     {

         dp[i][][] = dp[i - ][][] + (num[i] == );

         dp[i][][] = dp[i - ][][] + (num[i] == );

         for (int j = ; j <= times; j++)

         {

             ///第i秒，第j次换是0，不换是1

             dp[i][j][] = max(dp[i - ][j - ][], dp[i - ][j][]) + (num[i] == );///在第1棵树下，如果num[i]==1就+1

             dp[i][j][] = max(dp[i - ][j - ][], dp[i - ][j][]) + (num[i] == );///在第2棵树下，如果num[i]==2就+1

             maxsum = max(maxsum, max(dp[i][j][], dp[i][j][]));///第j次的时候在那棵树下最多

         }

     }

     printf("%d\n", maxsum);

     return ;

 }

巴特西

POJ 2385 DP

最新文章

热门文章