思路

重要信息是区间m次修改最多能产生2*m-1个区间
然后就成了简单dp了

代码


//f[j][i][0/1]表示到j这个点分了i段，这一段染色的是0/1的作业数
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+7;
int n,m;
ll ans;
ll a[maxn];
ll f[maxn][107][2];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<2*m;++i)
    {
        for(int j=1;j<=n;++j)
        {
            f[j][i][0] = max(f[j - 1][i][0], f[j - 1][i - 1][1]);
            f[j][i][1] = max(f[j - 1][i][1], f[j - 1][i - 1][0]);
            if(a[j]==1) f[j][i][1]++;
            else f[j][i][0]++;
            ans=max(ans,f[j][i][0]);
            ans=max(ans,f[j][i][1]);
        }
    }
    cout<<ans;
    return 0;
}