没太写过记忆化搜索。。。

//暴搜，每个时间点移动不移动，记忆化：if(mem[t][w][opt]) return mem[t][w][opt]
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[1010];
int mem[1010][20][2];
int dfs(int t,int w,int sum,int opt)//t表示当前时间点，w表示已经移动了的次数，sum表示收获的苹果数，opt表示当前在哪棵树
{
	if(t>n)
	{
		ans=max(ans,sum);
		return 0;
	}
	if(a[t]==1)//当前时间苹果树1掉果子 
	{
		if(opt==1)//正好在这棵树底下
		{
			if(w+1<=m)
			{
				dfs(t+1,w+1,sum+1,2);//走人;
			    dfs(t+1,w,sum+1,1);//待着 
			}
			else dfs(t+1,w,sum+1,1);
		} 
		else if(opt==2)//在另一棵树下 
		{
			if(w+1<=m)
			{
			    dfs(t+1,w+1,sum,1);//走人
			    dfs(t+1,w,sum,2);//待着 	
			}
			else dfs(t+1,w,sum,2);
		}
	} 
	else if(a[t]==2)//2掉果子 
	{
		if(opt==2)
		{
			if(w+1<=m)//如果可移动就有两种决策
			{
				dfs(t+1,w+1,sum+1,1);//走人
			    dfs(t+1,w,sum+1,2);//待着 
			}
			else dfs(t+1,w,sum+1,2);//只能待着 
		}
		else if(opt==1)
		{
			if(w+1<=m)
			{
				dfs(t+1,w+1,sum,2);//走人 
			    dfs(t+1,w,sum,1);//待着 
			}
			else dfs(t+1,w,sum,1);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]); 
	}
	dfs(1,0,0,1);
	cout<<ans;
	return 0;
}