栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

前缀和给我写麻了

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

前缀和给我写麻了

#include
#include
#include
using namespace std;
char mp[410][410];
int b[410][410],w[410][410];
int u[410],d[410];
int n,m;
int calw(int x1,int y1,int x2,int y2){
    return w[x2][y2]-w[x1-1][y2]-w[x2][y1-1]+w[x1-1][y1-1];
}
int calb(int x1,int y1,int x2,int y2){
    return b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1];
}
int cal(int l,int r)
{
    int ans=1e9;
    u[0]=d[0]=0;
    d[++d[0]]=n;
    for(int i=n-1;i;i--)
    {
        int hd =(d[d[0]]-i)-calb(i,l,d[d[0]]-1,l);
            hd+=(d[d[0]]-i)-calb(i,r,d[d[0]]-1,r);
            hd+=(r-l-1)-calb(d[d[0]],l+1,d[d[0]],r-1);
            hd+=(r-l-1)*(d[d[0]]-i)-calw(i,l+1,d[d[0]]-1,r-1);
        int hn =r-l-1-calb(i,l+1,i,r-1);
        if(hd>hn) d[++d[0]]=i;
    }
    u[++u[0]]=1;
    for(int i=2;i<=n;i++)
    {
        int hu =(i-u[u[0]])-calb(u[u[0]]+1,l,i,l);
            hu+=(i-u[u[0]])-calb(u[u[0]]+1,r,i,r);
            hu+=(r-l-1)-calb(u[u[0]],l+1,u[u[0]],r-1);
            hu+=(r-l-1)*(i-u[u[0]])-calw(u[u[0]]+1,l+1,i,r-1);
        int hn =r-l-1-calb(i,l+1,i,r-1);
        if(hu>hn) u[++u[0]]=i;
    }
    reverse(d+1,d+d[0]+1);
    int p=1;
    for(int i=1;i<=u[0];i++)
    {
        while(p<=d[0]&&d[p]-u[i]<4) p++;
        if(p>d[0]) break;
        int hf =(r-l-1)*(d[p]-u[i]-1)-calw(u[i]+1,l+1,d[p]-1,r-1);
            hf+=(r-l-1)-calb(u[i],l+1,u[i],r-1);
            hf+=(r-l-1)-calb(d[p],l+1,d[p],r-1);
            hf+=(d[p]-u[i]-1)-calb(u[i]+1,l,d[p]-1,l);
            hf+=(d[p]-u[i]-1)-calb(u[i]+1,r,d[p]-1,r);
        ans=min(ans,hf);
    }
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int ans=1e9;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                char c=getchar();
                while(c==' '||c=='n') c=getchar();
                mp[i][j]=c;
                b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+(mp[i][j]=='1');
                w[i][j]=w[i][j-1]+w[i-1][j]-w[i-1][j-1]+(mp[i][j]=='0');
            }

        for(int i=1;i<=m;i++)
            for(int j=i+3;j<=m;j++)
                ans=min(ans,cal(i,j));

        cout<
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/290007.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号