poj 2385 树上掉苹果问题 dp算法

题意：有树1 树2 会掉苹果，奶牛去捡，只能移动w次，开始的时候在树1 问最多可以捡多少个苹果？

思路： dp[i][j]表示i分钟移动j次捡到苹果的最大值

实例分析

0,1 1,2...说明偶数在树1 奇数在树2

for (int i = 1; i <= n; i++)
{
scanf("%d", &t[i]);
t[i] -= 1;
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= w; j++)
{
if (j % 2) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + t[i];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + !t[i];
}

这里有个小技巧，不是每次要求输入1 2 2 之类的数据，我们把它们都-1 然后就可以就比较好看了

解释一下两句dp语句

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) 表示上一次要么在树1 要么在树2的情况，但是我只需要它们两者之间的最大值

解决问题的代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int dp[][];

int t[];

int main()

{

    int n, w;

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

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

    {

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

        t[i] -= ;

    }

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

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

        {

            if (j % ) dp[i][j] = max(dp[i - ][j], dp[i - ][j - ]) + t[i];

            else dp[i][j] = max(dp[i - ][j], dp[i - ][j - ]) + !t[i];

        }

    printf("%d\n", dp[n][w]);

}

巴特西

poj 2385 树上掉苹果问题 dp算法

最新文章

热门文章