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

7 2
2
1
1
2
2
1
1

Sample Output

6

题解:

定义 $dp[i][j] :$ 前 i 秒转换 j 次的最多收集个数
对于状态转移, 我们有转换和不转换两种情况, 对于转换的话我们要判断能不能摘当前树, 也就是判断i, j奇偶性是否一致
即 $dp[i][j]=min(dp[i−1][j],dp[i−1][j−1]+1)$

注意起点是在一号树下

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
typedef pair<int,int> PII;
typedef long long LL;

const int N=1010;
int f[N];
int a[N];
int n,m;

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            f[j]=max(f[j],f[j-1]);
            if((j%2 == 1 && a[i] == 2) || (j%2 == 0 && a[i]==1))
                f[j]++;
        }

    cout<<f[m]<<endl;

   // system("pause");
}