POJ 2385

==>原题链接

题目概述

FJ在两棵苹果树下等着苹果，FJ开始在树1下，给出每个时刻苹果在哪棵树上掉下来，最多能移的次数，求最多能得到的苹果数。

思路

DP。

dpi = max(dpi-1, dpi-1) + rec;

表示前i时刻，移动j次，最多能得到的苹果数，他取决于 这一时刻是否移动 和 移动后是否取得此刻的苹果。

最后只要枚举各个移动次数，可取得最大值 比较输出即可。

（完整的思路☂，赞~）

“枚举 i个时刻 不同次数”，比较，新技能GET

代码

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int dp[1000+10][30+10],
    num[1000+10];
int main()
{
    int i, j;
    int n, w, rec, ans = 0;

    freopen("2385.in", "r", stdin);
    scanf("%d%d", &n, &w);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
    }

    memset(dp, 0, sizeof(dp));

    for (i = 1; i <= n; i++)
    {
        dp[i][0] = dp[i-1][0] + (num[i] & 1);
        for (j = 1; j <= i && j <= w; j++)
        {
            if (1 + j % 2 == num[i])
            {
                rec = 1;
            }
            else
            {
                rec = 0;
            }
            //rec = (1 + j & 1 + num[i]) & 1 ? 1:0;
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + rec;
        }
    }

    for (j = 1; j <=  w; j++)
    {
        ans = max(ans, dp[n][j]);
    }

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


    return 0;
}