DP 之 poj 2385

//  [3/24/2014 Sjm]
/*
先模拟一下测试用例：
时间   掉苹果的那棵树  对应时间下在跑了 w 次的情况下获得苹果的最大值
		       w  =  0(在1处)   1(在2处)    2(在1处)  

   Bessie 在哪里，就说明哪里的苹果可接
  1        2                 0             1           0
  2        1                 1             1           2
  3        1                 2             1           3          
  4        2                 2             3           3
  5        2                 2             4           3
  6        1                 3             4           5
  7        1                 4             4           6
定义： dp[i+1][j+1] := 在i+1的时间时，在跑了 j+1 次的情况下获得苹果的最大值
在考虑第 i+1 的时间点，已跑 j+1 次时，
分析：  

1） 第 i 的时间点时，已跑 j 次： 若在第 i+1 的时间点，再跑一次，即 j+1 次时，判断可否接到苹果；
2） 第 i 的时间点时，已跑 j+1 次： 若在第 i+1 的时间点，原地静止，判断可否接到苹果；
   （两者取最大值即答案）
综上： dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i][j]) + ((接到苹果) ? 1 : 0);

// 以下在 poj 上似乎没有被考虑（当然也可能我考虑错了），因为直接输出 dp[T][W] 亦可 AC
注： 
当在 T(即最大时间) 跑 j (0<=j<W)时， 亦可能取到最大值，并非一定是当在 T(即最大时间) 跑 W(即最多次数时) 次时，取得最大值。
例如测试数据：3 1211正确答案应是2 （dp[3][0]取得）,而非1 （dp[3][1]取得）。
*/

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_T = 1000, MAX_W = 30;
int T, W, myT[MAX_T + 1], myW[MAX_W + 1], dp[MAX_T + 1][MAX_W + 1];

int Solve()
{
    for (int i = 0; i < T; i++)
        for (int j = 0; j < W; j++)
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i][j]) + ((myT[i+1] == myW[j+1]) ? 1 : 0);
    int myMax = dp[T][0];
    for (int i = 1; i <= W; i++)
        myMax = max(myMax, dp[T][i]);
    return myMax;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d%d", &T, &W);
    for (int i = 0; i <= W; i++)
        myW[i] = ((i & 1) ? 2 : 1);
    for (int i = 1; i <= T; i++)
        scanf("%d", &myT[i]);
    for (int i = 1; i <= T; i++)
        dp[i][0] = dp[i - 1][0] + ((myT[i] == myW[0]) ? 1 : 0);
    printf("%d
", Solve());
    return 0;
}