POJ 2385(Apple Catching)

链接：https://vjudge.net/problem/POJ-2385#author=SCU2018

思路：dp题，首先找到状态转移关系，有dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])，如果此时所在位置还有苹果，那么dp[i][j]还需+1，注意最后输出的不一定是dp[t][m]，因为可能最大移动步数不需要用完，所以还需要dp[t][k]中寻找最大值。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int a[1001];
int dp[1001][31];

int main(){
    memset(dp,0,sizeof(dp));
    int t,m;
    cin>>t>>m;
  for(int i=1;i<=t;i++){
        cin>>a[i];
    }
    for(int i=1;i<=t;i++){
        for(int j=0;j<=m;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(j%2+1==a[i])dp[i][j]++;
    }
    }
    int ans = dp[t][0];
    for(int j=1;j<=m;j++){
        ans = max(ans,dp[t][j]);
    }
    cout<<ans<<endl;
    return 0;
}