题解 P2690 【接苹果】

ztzshiwo001219 · 2016-07-17 10:10:43 · 题解

这是一个比较简单的DP问题。。。我大概讲一下我的动态转移方程

dp[i][j]表示奶牛在第i分钟内转移了j次能够接到的最多苹果

那么显而易见，对于每一分钟来说，枚举转移次数从而得到解

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])同时如果 a[i]==j%2+1 即奶牛在这一分钟可以见到苹果 那么把dp[i][j]++

初始化是数组一开始都是0

最终的答案是到第T分钟时奶牛走1~w步能够取得的最多苹果

贴C++代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int dp[1010][31],T,w,a[1010],ans;
int main()
{
    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<=T&&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%2+1)dp[i][j]++;
        }
    for(int i=0;i<=w;i++)
        ans=max(ans,dp[T][i]);
    printf("%d\n",ans);
    return 0;
} 

其实应该可以边读入边计算DP 可以留给你们自己尝试 我是蒟蒻。。。