基础动态规划-POJ2385(Apple Catching)

描述

Description

It is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in his field, each full of apples. Bessie cannot reach the apples when they are on the tree, so she must wait for them to fall. However, she must catch them in the air since the apples bruise when they hit the ground (and no one wants to eat bruised apples). Bessie is a quick eater, so an apple she does catch is eaten in just a few seconds.

Each minute, one of the two apple trees drops an apple. Bessie, having much practice, can catch an apple if she is standing under a tree from which one falls. While Bessie can walk between the two trees quickly (in much less than a minute), she can stand under only one tree at any time. Moreover, cows do not get a lot of exercise, so she is not willing to walk back and forth between the trees endlessly (and thus misses some apples).

Apples fall (one each minute) for T (1 <= T <= 1,000) minutes. Bessie is willing to walk back and forth at most W (1 <= W <= 30) times. Given which tree will drop an apple each minute, determine the maximum number of apples which Bessie can catch. Bessie starts at tree 1.
Input

• Line 1: Two space separated integers: T and W

• Lines 2…T+1: 1 or 2: the tree that will drop an apple each minute.
  Output

• Line 1: The maximum number of apples Bessie can catch without walking more than W times.

实质上

是在求一个数组连续的奇数或者偶数位置的和，但是我们可以变换位置即，连续求奇数位置的和后变换到求偶数位置的和。变换的次数有限制不超过W次。

递推（控制问题规模）

仔细想想我们通过，位置i和次数w可以控制问题的规模，那么我们设dp[i][w] 为在位置i，并且我们变换了w次，最大的累计和。
dp[i][w]=max(dp[i-1][w-1]+dp[i-2][w])+cur[i]
可以这样理解，到当前位置为止，我们累计和，可以是来自上个为止的如果相差2，说明奇数偶数性没有改变，我们不需要用到次数，是上个位置i-2，次数还是w，如果来自i-1这个位置，说明到这个位置用了一次变换之后变换的总数是w，所以可能来自，i-1位置上，用了w-1次变换后的结果。
当然他们俩谁大取谁的值。

边界条件

需要注意我们人为的设置，比如在0的位置上，变换为1时候的值为-1，以此来约束。

代码实现

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;

int dp[1000/2+1][30+1];
int main(){
    int w,t;
    vector<int> apple;
    cin>>t>>w;
    int c=-1;
    
    for(int i=0;i<t;i++){
        cin>>c;
        apple.push_back(c);
    }
    
    vector<int> apple_sum;
    int cnt=0;
    for(int i=0;i<t;){
        c=apple[i];
        cnt=0;
        while(c<t&&apple[i]==c){
            cnt++;
            i++;
        }
        apple_sum.push_back(cnt);
    }
    
    //init
    dp[0][0]=apple_sum[0];
    dp[1][0]=apple_sum[1];
    for(int i=2;i<apple_sum.size();i++){
        dp[i][0]=dp[i-2][0]+apple_sum[i];
    }
    //对于移动了j>0次到达0位置的，我们人为的设置成-1，代表以这个为基础的后续问题，永远都不会达到最大。
    for(int j=1;j<=w;j++){
        dp[0][j]=-1;
    }
    
    
    for(int i=1;i<apple_sum.size();i++){
        for(int j=1;j<=w;j++){
            if(i-2>=0)
                dp[i][j]=max(dp[i-2][j],dp[i-1][j-1])+apple_sum[i];
            else
                dp[i][j]=dp[i-1][j-1]+apple_sum[i];
        }
    }
    int res=0;
    for(int i=0;i<=w;i++)
    {
        res=max(res,dp[apple_sum.size()-1][i]);
        res=max(res,dp[apple_sum.size()-2][i]);
    }
    cout<<res<<endl;
    return 0;
}