不过 程序没有判定 无解的情况(还要继续YY)，保证有解的情况全部正确，官方所有数据都是有解的。。(最后几组 I don't know 不太清楚，有解的话程序跑出来应该
就没有错)


#include<cstring>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
int dp[110000],neg,ans,inf=1000000000;
struct pp
{
   int id,value,ip;
   bool operator <(const pp &temp)const
   {
        if(value==temp.value)
            return ip<temp.ip;
        return value>temp.value;
   }
};
pp maxi[110000],queue[100000][20],tbd[110000],nls[110000],now[110000];
int iden[1000000],nu[110000],size,cnt,num[110000],n,m,mat[110000][11],sum[110000][11],vv[110000],nc[110000],np[110000];
int pos[110000],num_tb,cnt_now,dl[110000],cnt_dl;
void ins(int value,int id)
{
     int i,j,s,p,q;
     if(cnt==0||maxi[0].value==value)
     {
        maxi[cnt].id=id;
        maxi[cnt++].value=value;
        return;
     }
     if(maxi[0].value>value)
         return;
     maxi[0].value=value;
     maxi[0].id=id;
     cnt=1;
}
void del(pp list[],int &cnt)
{
     int i,j,s,p,q,nl=0;
     j=0;
     for(i=0;i<cnt;i++)//for(j=0;j<num_tb;j++)
     {
         if(j<num_tb&&list[i].id==tbd[j].id)
            j++;
         else
            nls[nl++]=list[i];
     }
     cnt=nl;
     for(i=0;i<cnt;i++)
        list[i]=nls[i];
}
int upper_bound(int id,int x,int y)
{
    if(3*x+y>=neg)
       return x+y;
    if(3*(x+dp[id])+y<=neg)
        return x+dp[id]+neg-3*(x+dp[id]);
    return neg-2*x;//x+y+neg-3*x-y;
}
int lower_bound(int id,int x,int y)
{
    if(3*x+y>=neg)
        return x+y;
    if(3*(x+dp[id])+y>=neg)
        return y+(neg-y+2)/3;
    return x+dp[id]+neg-3*(x+dp[id]);
}
void insert(int ie,int id,pp now)
{
     int i,j,s,p,q,ip,px,py,nx,ny,x=now.value,y=ie-now.value;
     if(pos[id]>=0)
        ip=pos[id];
     else
     {
        ip=size;
        iden[size]=now.ip;
        pos[id]=size++;
     }
     if(nu[ip]==0)
         queue[ip][nu[ip]++]=now;
     else
     {
         if(queue[ip][0].value>now.value)
             return ;
         if(queue[ip][0].value<now.value)
         {
             queue[ip][0]=now;
             nu[ip]=1;
             return;
         }
         queue[ip][nu[ip]++]=now;
     }
}
int solve()
{
    int i,j,s,p,q,x,y,nx,ny,id,ip;
    bool ok; 
    memset(pos,-1,sizeof(pos));
    memset(nu,0,sizeof(nu));
    queue[0][0].id=0;
    queue[0][0].value=0;
    queue[0][0].ip=0;
    iden[0]=0;
    pos[0]=0;
    nu[0]=1;
    size=1;
    ans=upper_bound(0,0,0);
    
   // printf("orz=%d\n",lower_bound(0,0,0));
 //  printf("dp[0]=%d,neg=%d\n",dp[0],neg);
    for(i=0;i<n;i++)
    {
        cnt_now=0;
        for(j=0;j<size;j++)
        {
            num_tb=0;
            ok=false;
            ip=iden[j]+1;
            for(s=0;s<nu[j];s++)
            {
                id=queue[j][s].id; 
                x=queue[j][s].value;
                if(np[id]==np[i+1]||id==i)
                {
                    if(id==i)
                    {
                        nx=x;
                        ok=true;
                    }
                    else
                    {
                       int vx=sum[id][0]-sum[i+1][0];
                       for(p=1;p<m;p++)
                       {
                          if(vx<=sum[id][p]-sum[i+1][p])
                            break;
                       }
                       if(p>=m)
                       {
                          ok=true;
                          nx=x+1;
                        // if(i==77)
                          //   printf("x=%d\n",x);
                          break;
                       }
                       if(lower_bound(i+1,x+1,i-x-ip)>=ans)
                       {
                         // if(x+1==2)
                           //  printf("ans=%d\n",ans);
                          tbd[num_tb++]=queue[j][s];
                       }
                    }
                }
                else
                    tbd[num_tb++]=queue[j][s];
            }
            x=nx-1;
            del(queue[j],nu[j]);
            //if(nu[j]==0)
              // puts("orz");         
            if(ok)
            {
                 now[cnt_now].id=i+1;
                 now[cnt_now].value=x+1;
                 now[cnt_now].ip=ip;
                 y=i-x-ip;
                 if(y>=0)
                 {
                    ans=min(ans,upper_bound(i+1,x+1,y));
                    if(lower_bound(i+1,x+1,y)<ans)
                       cnt_now++;//   insert(i+1,j+1,now);
                 }
            }
        }
        int nc=0;
        for(j=0;j<cnt_now;j++)
        {
             x=now[j].value;
             y=i+1-x-now[j].ip;
             if(lower_bound(i+1,x,y)<ans)
                  now[nc++]=now[j];
        }
        cnt_now=nc;
        int px,py;
        for(j=0;j<cnt_now;j++)
        {
              x=now[j].value;
              y=i+1-x-now[j].ip;
              if(j==0||py>y)
              {
              
             // printf("i=%d,x=%d,y=%d,ip=%d\n",i,x,y,now[j].ip);
                  insert(i+1,now[j].ip,now[j]);
                  px=x;
                  py=y;
              }
        }
    }
    if(ans==inf)
       ans=-1;
    return ans;
}
int main()
{
    int i,j,s,p,q,id,ww;
     //  freopen("debug\\input.txt","r",stdin);
   // freopen("debug\\output.txt","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
       for(j=0;j<m;j++)
          scanf("%d",&mat[i][j]);
    memset(dp,0,sizeof(dp));
    memset(sum,0,sizeof(sum));
    memset(nc,0,sizeof(nc));
    memset(np,0,sizeof(np));
    neg=0;
    for(i=n-1;i>=0;i--)
    {
        for(j=0;j<m;j++)
            sum[i][j]=sum[i+1][j]+mat[i][j];
        for(j=1;j<m;j++)
        {
            if(mat[i][0]<=mat[i][j])
                break;
        }
        if(j>=m)
            vv[i]=1;
        else
            vv[i]=-1;
        neg+=vv[i];
        nc[i]=nc[i+1];
        np[i]=np[i+1];
        if(vv[i]<0)
           nc[i]++;
        else
           np[i]++;
    }
    if(neg>0)
       printf("0\n");
    else
    {
        neg=-neg;
        neg++;
        memset(num,0,sizeof(num));
        maxi[0].value=0;
        maxi[0].id=n;
        cnt=1;
        for(i=n-1;i>=0;i--)
        {
           num_tb=0;
           for(j=0;j<cnt;j++)
           {
              id=maxi[j].id;
              int vx=sum[i][0]-sum[id][0];
              if(np[i]!=np[id]||id==i+1)
              {
                 ww=0;
                 if(np[i]!=np[id])
                    tbd[num_tb++]=maxi[j];
                 //puts("you");
              }
              else//if(np[i]==np[id])
              {
                 for(s=1;s<m;s++)
                 {
                   if(vx<=sum[i][s]-sum[id][s])
                       break;
                 }
                 if(s>=m)
                     ww=1;
                 else
                     ww=0;
              }
              if(dp[i]<maxi[j].value+ww)
              {
                 dp[i]=maxi[j].value+ww;
                 if(ww==1)
                    break;
              }
           }
           del(maxi,cnt);
           
          // printf("i=%d,dp=%d,neg=%d\n",i,dp[i],neg);
           
           ins(dp[i],i);
       }
      // puts("orz");
       printf("%d\n",solve());
    }
   // system("pause");
    return 0;
}
/*
5
4
3 0 4 0
5 6 1 0
7 0 0 9
2 0 3 0
4 5 0 0


*/

• Re:自己YY了一个很NB的算法，官方数据全秒 (60) tasty 2014-07-28 14:47:48
  • Re:自己YY了一个很NB的算法，官方数据全秒 (197) tasty 2014-07-28 16:03:58
    • 去参加百度之星一了吗？ (139) yygy 2014-07-28 20:35:23
      • Re:去参加百度之星一了吗？ (72) tasty 2014-07-28 20:36:06
        • 是困难啊。数据太多了。而且出题根本不知道你会用什么方法做。如果不是世界级顶尖高手，不好造啊。这出题人最后几个数据也没有出来。说明他的水平还没有达到世界级顶尖啊。 (80) yygy 2014-07-28 20:53:46
          • Re:是困难啊。数据太多了。而且出题根本不知道你会用什么方法做。如果不是世界级顶尖高手，不好造啊。这出题人最后几个数据也没有出来。说明他的水平还没有达到世界级顶尖啊。 (66) tasty 2014-07-28 20:55:31
            • Re:是困难啊。数据太多了。而且出题根本不知道你会用什么方法做。如果不是世界级顶尖高手，不好造啊。这出题人最后几个数据也没有出来。说明他的水平还没有达到世界级顶尖啊。 (110) tasty 2014-07-28 21:00:37