蓝桥杯备考----＞ Apple Catching G(线性DP）
每分钟都掉一个苹果，可能是在1树也可能在2树，移动次数有限，我们可以用线性dp来做
又因为我们知道了初始位置是树1，那说明我们移动1次是到2，移动2次是到1，移动3次再到2，也就是说移动奇数次就是到2，移动偶数次就是到1
好，我们按照动态规划的步骤来想一下
step1:定义状态表示 f[i][j]表示，表示的是在移动j次接到的苹果数量
step2:推导状态转移方程
step3:初始化
全部初始化为0就行
实现代码：👇
#include <iostream>
using namespace std;
const int N = 1010;
int t,w;
int f[N][N];
int a[N];
int main()
{
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++)
{
int c = 0;
if((j%2==0 && a[i]==1) || (j%2==1) && a[i]==2) c= 1;
f[i][j] = f[i-1][j]+c;
if(j)
{
f[i][j] = max(f[i][j],f[i-1][j-1]+c);
}
}
}
int ret = 0;
for(int j=0;j<=w;j++)
{
ret = max(ret,f[t][j]);
}
cout << ret << endl;
return 0;
}