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）

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 int num[1005];
 5 int dp[1005][35][2];
 6 int main()
 7 {
 8     int n, times, maxsum = -1;
 9     scanf("%d%d", &n, &times);
10     for (int i = 1; i <= n; i++)
11         scanf("%d", &num[i]);
12     for (int i=1; i<=n; i++)
13     {
14         dp[i][0][0] = dp[i - 1][0][0] + (num[i] == 1);
15         dp[i][0][1] = dp[i - 1][0][1] + (num[i] == 2);
16         for (int j = 1; j <= times; j++)
17         {
18             ///第i秒，第j次换是0，不换是1
19             dp[i][j][0] = max(dp[i - 1][j - 1][1], dp[i - 1][j][0]) + (num[i] == 1);///在第1棵树下，如果num[i]==1就+1
20             dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]) + (num[i] == 2);///在第2棵树下，如果num[i]==2就+1
21             maxsum = max(maxsum, max(dp[i][j][0], dp[i][j][1]));///第j次的时候在那棵树下最多
22         }
23     }
24     printf("%d
", maxsum);
25     return 0;
26 }

View Code