【BZOJ3791】作业
Description
众所周知，白神是具有神奇的能力的。
比如说，他对数学作业说一声“数”，数学作业就会出于畏惧而自己完成；对语文作业说一声“语”，语文作业就会出于畏惧而自己完成。
今天，语文老师和数学老师布置了许多作业，同学们纷纷寻找白神寻求帮助。白神作为一个助人为乐的人，便答应下来。
回到家，白神将这N份作业按顺序摊开，发现语文作业数学作业混在一起，这就让白神苦恼起来，他如果对连续一段作业喊出“数”，那么里面的语文作业就会由于过于慌乱而写满错解，不过如果白神再对其喊一声“语”，它又会写满正确答案。
虽然白神很强大，但是能力还是有限制的，一天只能使用K次，现在，白神想知道他能正确的完成多少份作业。
Input
第一行两个整数N，K。
第二行N个0或者1表示这份作业是语文作业还是数学作业。
Output
输出一个整数，表示白神能正确完成的作业数。
Sample Input
5 2
0 1 0 1 0
0 1 0 1 0
Sample Output
4
HINT
100%的数据中N ≤ 100000，K<=50.
题解：我们先来寻找一个非常显然的结论：
如果只能喊1次，那么只能完成：若干个0
如果能喊2次，那么可以完成：若干个0-若干个1-若干个0
以此类推，如果能喊n次，那么采用最后的策略可以完成：若干个0-若干个1-若干个0...若干个0
即：如果能喊n次，那么在我们能正确完成的作业中，0和1的改变最多出现2*(n-1)次。
那么设f[i][j][0/1]表示前i份作业，已经改变了j次，最后一个完成的作业是0/1，所能完成的最多作业数，然后转移即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=100010;
int n,k,ans;
int v[maxn],f[maxn][100][2];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),k=rd()*2-1;
int i,j,d;
for(i=1;i<=n;i++) v[i]=rd();
f[1][1][0]=!v[1],f[1][1][1]=v[1];
for(i=2;i<=n;i++)
{
d=v[i];
for(j=1;j<=k;j++)
{
f[i][j][0]=f[i-1][j][0]+(!d);
if(!d) f[i][j][0]=max(f[i][j][0],f[i-1][j-1][1]+1);
f[i][j][1]=f[i-1][j][1]+d;
if(d) f[i][j][1]=max(f[i][j][1],f[i-1][j-1][0]+1);
ans=max(ans,max(f[i][j][0],f[i][j][1]));
}
}
printf("%d",ans);
return 0;
}