牛客练习赛29 B 列队

【题解】

　　把某一行或某一列有4个1的都统计出来，然后首尾接上尽量长的，注意首尾不能选上同一个矩阵，要维护前缀、后缀1最大值和次大值。

　　还要注意维护矩阵内连续1的长度，因为可能有 0 0 0 0 这种情况。

　　　　　　　　　　　　　　　　　　　　　　   0 1 1 0

　　　　　　　　　　　　　　　　　　　　　　   0 1 1 0

　　　　　　　　　　　　　　　　　　　　　　   0 0 0 0

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 #define rg register

 #define N 200010

 using namespace std;

 int n,m,b[][],ans[][],f[],pos,pos2,Mx;

 bool v[][];

 struct rec{

     int l,r;

 }s[N][][];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 int main(){

     n=read();

     for(rg int i=;i<=n;i++){

         memset(v,,sizeof(v));

         for(rg int j=;j<;j++)

             for(rg int k=;k<;k++) b[j][k]=read();

         if(b[][]||b[][]){

             int tmp=;

             if(b[][]&&b[][]) tmp++;

             Mx=max(Mx,tmp);

         }

         if(b[][]||b[][]){

             int tmp=;

             if(b[][]&&b[][]) tmp++;

             Mx=max(Mx,tmp);

         }

         if(b[][]||b[][]){

             int tmp=;

             if(b[][]&&b[][]) tmp++;

             Mx=max(Mx,tmp);

         }

         if(b[][]||b[][]){

             int tmp=;

             if(b[][]&&b[][]) tmp++;

             Mx=max(Mx,tmp);

         }

         for(rg int j=;j<;j++){

             bool ok=;

             for(rg int k=;k<;k++)if(!b[j][k]) ok=;

             if(ok) ans[][j]+=,v[][j]=;

         }

         for(rg int j=;j<;j++){

             bool ok=;

             for(rg int k=;k<;k++)if(!b[k][j]) ok=;

             if(ok) ans[][j]+=,v[][j]=;

         }

         for(rg int j=;j<;j++){

             if(v[][j]) continue;

             for(rg int k=;k<;k++)if(b[j][k]){

                 s[i][][j].l++;

             }

             else break;

             for(rg int k=;k>=;k--)if(b[j][k]){

                 s[i][][j].r++;

             }

             else break;

         }

         for(rg int j=;j<;j++){

             if(v[][j]) continue;

             for(rg int k=;k<;k++)if(b[k][j]){

                 s[i][][j].l++;

             }

             else break;

             for(rg int k=;k>=;k--)if(b[k][j]){

                 s[i][][j].r++;

             }

             else break;

         }

 //        for(rg int j=0;j<4;j++) printf("-%d ",s[i][0][j].l); puts("l");

 //        for(rg int j=0;j<4;j++) printf("-%d ",s[i][0][j].r); puts("r");

 //        for(rg int j=0;j<4;j++) printf("+%d ",s[i][1][j].l); puts("l");

 //        for(rg int j=0;j<4;j++) printf("+%d ",s[i][1][j].r); puts("r");

     }

     for(rg int j=;j<;j++){

         for(rg int k=;k<;k++){

             int mx=,mx2=,pos=,pos2=,mx3=,mx4=;

             for(rg int i=;i<=n;i++){

                 if(s[i][j][k].l>mx){

                     mx=s[i][j][k].l;

                     pos=i;

                 }

             }

             for(rg int i=;i<=n;i++){

                 if(s[i][j][k].l>mx2&&i!=pos) mx2=s[i][j][k].l;

             }

             for(rg int i=;i<=n;i++){

                 if(s[i][j][k].r>mx3){

                     mx3=s[i][j][k].r;

                     pos2=i;

                 }

             }

             for(rg int i=;i<=n;i++){

                 if(s[i][j][k].r>mx4&&i!=pos2) mx4=s[i][j][k].r;

             }

             if(pos!=pos2) ans[j][k]+=mx+mx3;

             else ans[j][k]+=max(mx+mx4,mx2+mx3);

 //            printf("[%d %d %d %d]\n",mx,mx2,mx3,mx4);

         }

     }

     for(rg int i=;i<;i++)

         for(rg int j=;j<;j++) Mx=max(Mx,ans[i][j]);

     printf("%d\n",Mx);

     return ;

 }