这题只需枚举一条中间线，将整个田地分成两半 然后分别计算两边对于某一个 i，vali 的最大值即可 i 为百合花的数量与牵牛花的数量之差 vali为区域内花的数量之和 而后只需要扫一遍所有可行的的情况取最大值即可 代码如下：
#include<bits/stdc++.h> using namespace std; #define M 35 #define N 905 #define Max(a,b) if(a<b)a=b char str[M]; int A[M][M]; int n,m,k,ans=-1; int sum[M][M],f[M][M]; int val1[N*2],val2[N*2]; void solve1(int x){ memset(val1,-1,sizeof(val1)); memset(val2,-1,sizeof(val2)); for(int a=1;a<=x;a++) for(int b=a;b<=x;b++) for(int c=1;c<=m;c++) for(int d=c;d<=m;d++){ int F=f[b][d]-f[b][c-1]-f[a-1][d]+f[a-1][c-1], SUM=sum[b][d]-sum[b][c-1]-sum[a-1][d]+sum[a-1][c-1]; Max(val1[F+N],SUM); } for(int a=x+1;a<=n;a++) for(int b=a;b<=n;b++) for(int c=1;c<=m;c++) for(int d=c;d<=m;d++){ int F=f[b][d]-f[b][c-1]-f[a-1][d]+f[a-1][c-1], SUM=sum[b][d]-sum[b][c-1]-sum[a-1][d]+sum[a-1][c-1]; Max(val2[F+N],SUM); } for(int i=-n*m;i<=n*m;i++){ if(val1[i+N]==-1)continue; int res=-1; for(int j=max(-k-i,-n*m);j<=min(n*m,k-i);j++) Max(res,val2[j+N]); if(~res)Max(ans,res+val1[i+N]); } } int solve2(int x){ memset(val1,-1,sizeof(val1)); memset(val2,-1,sizeof(val2)); for(int a=1;a<=n;a++) for(int b=a;b<=n;b++) for(int c=1;c<=x;c++) for(int d=c;d<=x;d++){ int F=f[b][d]-f[b][c-1]-f[a-1][d]+f[a-1][c-1], SUM=sum[b][d]-sum[b][c-1]-sum[a-1][d]+sum[a-1][c-1]; Max(val1[F+N],SUM); } for(int a=1;a<=n;a++) for(int b=a;b<=n;b++) for(int c=x+1;c<=m;c++) for(int d=c;d<=m;d++){ int F=f[b][d]-f[b][c-1]-f[a-1][d]+f[a-1][c-1], SUM=sum[b][d]-sum[b][c-1]-sum[a-1][d]+sum[a-1][c-1]; Max(val2[F+N],SUM); } for(int i=-n*m;i<=n*m;i++){ if(val1[i+N]==-1)continue; int res=-1; for(int j=max(-k-i,-n*m);j<=min(n*m,k-i);j++) Max(res,val2[j+N]); if(~res)Max(ans,res+val1[i+N]); } } int main(){ scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=n;i++){ scanf("%s",str+1); for(int j=1;j<=m;j++){ if(str[j]=='L')A[i][j]=1; else if(str[j]=='P')A[i][j]=-1; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ f[i][j]=f[i-1][j]+f[i][j-1]+A[i][j]-f[i-1][j-1]; sum[i][j]=sum[i-1][j]+sum[i][j-1]+(A[i][j]!=0)-sum[i-1][j-1]; } for(int i=1;i<n;i++)solve1(i); for(int j=1;j<m;j++)solve2(j); printf("%d\n",ans); return 0; }