poj 2385 Apple Catching

题目链接：http://poj.org/problem?id=2385

题目分类：动态规划

代码：

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int dp[1005][31][3];
int x[1005];


int main()
{
    int t, w;
    scanf("%d %d", &t, &w);
    for(int i=1;i<=t;i++)
        scanf("%d", &x[i]);
    //开三维的dp数组   dp[i][j][0]代表时刻i  步数j  在第二颗树下  dp[i][j][1]代表时刻i  步数j  在第一颗树下面 

    memset(dp, 0, sizeof(dp));
    for(int i=1;i<=t;i++)
    {
        for(int j=0;j<=w;j++)
        {
            if(j==0)
            {
                dp[i][0][1] = dp[i-1][0][1] + 2 - x[i]; 
                continue;
            }
            if(j%2==0)    //刚开始想的时候并没有考虑到这点，到达树1一定经过偶数步，到达数2一定经过奇数步
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]) + 2 - x[i];
            else
                dp[i][j][0] = max(dp[i-1][j-1][1], dp[i-1][j][0]) + x[i] - 1;
        }
    }
    int ans = max(dp[t][w][0], dp[t][w][1]);
    cout<<ans;
    return 0;
}