RT，思路是暴力预处理出每个可选区间 $sum_{l,r}$，然后 dfs 预处理出第 $i$ 行选 $j$ 次的最大值 $a_{i,j}$，最后对 $a_{i,j}$ 做背包。

这个做法的瓶颈就在 dfs 剪枝。

设 $ln$ 为当前可选区间的左端点，下记 $vis_{ln,ti}$ 为已知所有方案中的最大答案，当前状态已选取答案为 $ans$。

我分别使用了两种不同剪枝：

剪枝一： $vis_{ln,ti} \le vis_{ln-1,ti}$ 或 $vis_{ln,ti} \le vis_{ln,ti-1}$ 时，停止搜索。

剪枝二:$ans \le vis_{ln,ti}$ 时，停止搜索。

我开始一直试图使用剪枝一，但是总是 WA 70pts左右。后来换用剪枝二，就 AC 了。

但是事实上，我用剪枝一的代码和题解对拍了 5000+ 组，并没有拍出任何问题。

所以求助一下剪枝一为啥错了/yiw

附上剪枝一 70pts 代码：

#include<bits/stdc++.h>
#define ll long long
#define back return
#define ri register int
#define ull unsigned ll
using namespace std;
ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	back x*f;
}
char c;
int n,m,t,cnt[55],l[55],r[55],sum[55][55];
int dp[55][2550],a[55][55],re[55][55];
int vis[55][55];
void dfs(int now,int tag,int ln,int ti,int ans)
{
	if(ti==tag||ln>cnt[now])
	{	
		a[now][tag]=max(a[now][tag],ans);
		back ;
	}	
	if(ans+(m-l[ln]+1)<=a[now][tag])
		back ; 
	if(vis[ln][ti]&&(vis[ln-1][ti]>=vis[ln][ti]||vis[ln][ti]<=vis[ln][ti-1]))//该位置改成剪枝二就 AC 了
		back ;
	vis[ln][ti]=max(vis[ln][ti],ans);
	for(ri i=ln;i<=cnt[now];i++)
		if(sum[l[ln]][r[i]])
			dfs(now,tag,i+1,ti+1,ans+sum[l[ln]][r[i]]);		
	back ; 
}
int main()
{
	//freopen("data.in","r",stdin);
	//freopen("my.out","w",stdout);
	n=read(),m=read(),t=read();
	for(ri i=1;i<=n;i++)
		for(ri j=1;j<=m;j++)
			cin>>c,re[i][j]=c-'0';
	for(ri i=1;i<=n;i++)
	{	
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		memset(sum,0,sizeof(sum));
		l[++cnt[i]]=1;
		if(m==1)
			r[cnt[i]]=1;
		for(ri j=2;j<=m;j++)
		{		
			if(re[i][j]!=re[i][j-1])
			{
				r[cnt[i]]=j-1;
				l[++cnt[i]]=j;
			}	
			if(j==m)
				r[cnt[i]]=j;
		}
		for(ri k=1;k<=cnt[i];k++)
			for(ri j=k;j<=cnt[i];j++)
			{
				int s=j-k+1;
				if(s%2)
					sum[l[k]][r[j]]=sum[l[k]][r[j-1]]+(r[j]-l[j]+1);
				else
					sum[l[k]][r[j]]=sum[l[k]][r[j-1]];
			}
		for(ri k=1;k<=cnt[i];k++)
			for(ri j=k;j<=cnt[i];j++)
				sum[l[k]][r[j]]=max(sum[l[k]][r[j]],(r[j]-l[k]+1)-sum[l[k]][r[j]]);
		for(ri j=1;j<=min(cnt[i],t);j++)
		{	
			memset(vis,0,sizeof(vis));
			dfs(i,j,1,0,0);	
		}		
	}
	for(ri i=1;i<=n;i++)
		for(ri j=1;j<=t;j++)
			for(ri k=0;k<=min(cnt[i],j);k++)
				dp[i][j]=max(dp[i][j],dp[i-1][j-k]+a[i][k]);
	cout<<dp[n][t]<<"\n"; 
	back 0;
}