【POJ - 2385】Apple Catching（动态规划）

佚名 5年前 (2019-08-11) 算法 1192人围观抢沙发百度已收录

Apple Catching

直接翻译了

Descriptions

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

有两棵APP树,编号为1,2.每一秒,这两棵APP树中的其中一棵会掉一个APP.每一秒,你可以选择在当前APP树下接APP,或者迅速移动到另外一棵APP树下接APP(移动时间可以忽略不计),但由于却乏锻炼,你最多移动W次.问在T秒内,你最多能收集多少个APP.假设你开始站在1号APP树下.

Input

第1行：两个整数T（1 < = T< = 1000）和W（1 < = W< = 30）
第2..T+1行：1或2，代表每分钟掉落APP的那棵树的编号

Output

一行一个整数，代表你移动不超过W次能接住的最大APP数

Sample Input

Sample Output

题目链接

https://vjudge.net/problem/POJ-2385

定义dp[i][j]为在第i秒，移动j次获得的最大苹果数。在零时刻时，所有的dp项均为0。

当j为0时，有dp[i][j] = dp[i - 1][j]当j不为0时，有dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1])，即在 i - 1 时刻时，均有两种选择，一种选择移动，一种选择不移动。

注意题目并不是在移动越多次能获得越多苹果。

dp[i][j]标示在时间i，已经来回了j次时的最大苹果数目。这样dp方程肯定苹果数目不会变的，所以要注意，如果当前的次数刚到当前树下，dp[i][j]++

a[i]-(j&1)==1 判断当前的次数刚到当前树下

开始在1号树下，移动时，当j为奇数时，在2号树下

　　　　　　　　　　　 当j为偶数时，在1号树下

当j为奇数时，j&1为1，若a[i]为2，则当前的次数刚到当前树下，此时a[i]-(j&1)==1

当j为偶数时，j&1为0，若a[i]为1，则当前的次数刚到当前树下，此时a[i]-(j&1)==1

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 10005
using namespace std;
int T,W;
int ans;
int dp[Maxn][35];
int a[Maxn];
int main()
{
    MEM(dp,0);
    cin>>T>>W;
    for(int i=1;i<=T;i++)
        cin>>a[i];
    for(int i=1;i<=T;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if(j==0)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);//状态转移方程
            if(a[i]-(j&1)==1)
                dp[i][j]++;
        }
    }
    ans=dp[T][0];
    for(int i=1;i<=W;i++)//判断移动几次的APP最多
        ans=max(ans,dp[T][i]);
    cout<<ans<<endl;
    return 0;
}