Problem - 1580A - Codeforcest
题目大意
一个01矩阵 你可以花费一个时间让某个0变成1 某个1变成0
问你如何选择才能用最少的操作形成类似于我的世界地狱门的最小矩形
题目思路
首先处理二维前缀和
然后枚举上行w和下行s
然后预处理 F数组
设lr为左右界
f [i] 该数组意为L为1并且，R至少大于i的前缀和的最小值
然后枚举左界L 用R至少大于等于L+3的F数组去减去1-L的部分
时间复杂度 n*n*n
for(int k=1;k+3<=m;k++)
{int tmp=f[k+3]-(getsum(i+1,1,j-1,k)+k*2-getsum(i,1,i,k)-getsum(j,1,j,k))+(j-i-1)-getsum(i+1,k,j-1,k);ans=min(ans,tmp);
}代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=405;
int mp[maxn][maxn];
int sum[maxn][maxn],f[maxn];
int T,n,m;
void init()
{for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){sum[i][j]=mp[i][j]=0;f[j]=0;}}
}
inline int getsum(int lx,int ly,int rx,int ry)
{return sum[rx][ry]-sum[rx][ly-1]-sum[lx-1][ry]+sum[lx-1][ly-1];
}
int main()
{cin>>T;while(T--){cin>>n>>m;init();string s;for(int i=1;i<=n;i++){cin>>s;for(int j=1;j<=s.size();j++){int t=s[j-1]-'0';mp[i][j]=t;sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];}}int ans=1e9;for(int i=1;i<n;i++){for(int j=i+4;j<=n;j++){for(int k=4;k<=m;k++){f[k]=getsum(i+1,1,j-1,k-1)+(k-1)*2-getsum(i,1,i,k-1)-getsum(j,1,j,k-1)+j-i-1-getsum(i+1,k,j-1,k);//计算的依次是中间的空白 上下的边缘和 右边的边缘 （左边缘不计算） }for(int k=m-1;k>=4;k--){f[k]=min(f[k],f[k+1]);}for(int k=1;k+3<=m;k++){int tmp=f[k+3]-(getsum(i+1,1,j-1,k)+k*2-getsum(i,1,i,k)-getsum(j,1,j,k))+(j-i-1)-getsum(i+1,k,j-1,k);ans=min(ans,tmp);}}}cout<<ans<<endl;}return 0;
}