https://vjudge.net/problem/POJ-2385
猛刷简单dp的第一天的第一题。
状态：dp[i][j]表示第i秒移动j次所得的最大苹果数。关键要想到移动j次，根据j的奇偶判断人在哪里。
想了挺久的，最后还是参考了一篇和自己思路最近的代码https://blog.csdn.net/hellohelloc/article/details/52050207
我比他缺少的是特判dp[i][0]的状态，后面的一切都以此为基础的。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int a[], dp[][];
int main()
{
memset(dp, , sizeof(dp));
int n, m;
cin >> n >> m;
for(int i = ; i <= n; i++){
cin >> a[i];
}
for(int i = ; i <= n; i++){
dp[i][] = dp[i-][];
if(a[i] == ){//苹果在左边
dp[i][]++;
for(int j = ; j <= m; j++){
if(j&)//人在右边
dp[i][j] = max(dp[i-][j], dp[i-][j-]);
else//人在左边
dp[i][j] = max(dp[i-][j], dp[i-][j-])+;
}
}
else{//苹果在右边
for(int j = ; j <= m; j++){
if(j&)//人在右边
dp[i][j] = max(dp[i-][j], dp[i-][j-])+;
else//人在左边
dp[i][j] = max(dp[i-][j], dp[i-][j-]);
}
}
}
int maxm = -INF;
for(int i = ; i <= m; i++){
maxm = max(maxm, dp[n][i]);
}
cout << maxm << endl;
return ;
}