Apple Catching

直接翻译了

Descriptions

有两棵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][];

int a[Maxn];

int main()

{

    MEM(dp,);

    cin>>T>>W;

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

        cin>>a[i];

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

    {

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

        {

            if(j==)

                dp[i][j]=dp[i-][j];

            else

                dp[i][j]=max(dp[i-][j],dp[i-][j-]);//状态转移方程

            if(a[i]-(j&)==)

                dp[i][j]++;

        }

    }

    ans=dp[T][];

    for(int i=;i<=W;i++)//判断移动几次的APP最多

        ans=max(ans,dp[T][i]);

    cout<<ans<<endl;

    return ;

}

巴特西

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

Apple Catching

最新文章

热门文章