POJ 2385 Apple Catching(动态规划)

Description

有两棵苹果树,编号为1,2。每一秒,这两棵苹果树中的其中一棵会掉一个苹果。

每一秒,你可以选择在当前苹果树下接苹果,或者迅速移动到另外一棵苹果树下接苹果(移动时间可以忽略不计)。

但由于却乏锻炼,你最多移动W次.问在T秒内,你最多能收集多少个苹果.

假设你开始站在1号苹果树下.

DP步骤

状态设定

初始化

状态转移

DP优化(可无)

一.状态设定

根据DP要素决定DP维数

根据数据范围合理选择DP对象

根据难易程度选择DP顺序

Analyze

1DP要素：时间T、移动次数W(根据输入Input也能看出来)

2DP对象：数据都比较小，就是对T、W进行动态规划

3DP顺序：

先T后W：dp[t][w]前t秒移动w次的最优结果

先W后T：dp[w][t]移动w次…t秒…怪怪的…

其实存在时间元素时，这一元素一般放在第一维

二.初始化

我们dp从1开始时看0状态是不是0，是则初始化为0，否则初始化为相应值，本题初始状态默认为0

三.状态转移

dp[i][j]表示前i秒移动j次能接到的最多的苹果数

我们发现在设计的DP里“移动”是一个必定发生的事件，移动对应状态改变。那么移动之前怎么由之前的状态向之后的状态过渡呢？

前一个状态(第i - 1秒)也有两种决策：j(第i - 1秒移动，最多数目)，j - 1(第i - 1秒不动，最多数目)，分别对应dp[i - 1][j]和dp[i - 1][j - 1]，那么移动前的dp[i][j]取两者max。

另外根据移动次数判断在哪棵树下，根据输入判断此刻在这棵树下是否能接到苹果，能则dp[i][j]++

DP与递归

dp前i秒移动w次，我们并不需要知道那w次是在哪几秒里的，但是不耽误DP，这就是它(DP)的神秘之处——理论AC就能AC，不需要知道过程

这与递归函数的设计是极为相似的：

在设计之初便想好了它的功能与元素对应关系(各形参、DP各维的意义)，先理论AC再手动实现

像是一个封装好的东西，明明就是你自己封装的，你也知道它怎么用，就是不甚清楚它的运行过程、各处细节，但偏偏就是能用

Code

#include <cstdio>
#include <iostream>
using namespace std;

int a[1005];
int dp[1005][40];

int main()
{
    int t, w;
    scanf("%d%d", &t, &w);
    for(int i = 1; i <= t; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= t; ++i)
        for(int j = 0; j <= w; ++j)///可取0可取w
        {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
            if( ((j & 1) && (a[i] == 2)) || (j % 2 == 0 && a[i] == 1) )
                dp[i][j]++;
        }
    cout << dp[t][w] << '\n';
    return 0;
}

四.DP优化

转移方程dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);i完全是由i - 1转移来的，那么正序遍历可省略第一维

Code(Improved)

#include <cstdio>
#include <iostream>
using namespace std;

int a[1005];
int dp[40];

int main()
{
    int t, w;
    scanf("%d%d", &t, &w);
    for(int i = 1; i <= t; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= t; ++i)
        for(int j = 0; j <= w; ++j)///可取0可取w
        {
            dp[j] = max(dp[j], dp[j - 1]);
            if( ((j & 1) && (a[i] == 2)) || (j % 2 == 0 && a[i] == 1) )
                dp[j]++;
        }
    cout << dp[w] << '\n';
    return 0;
}