p1011.cpp

vijos动态规划5题:P1002,P1006,P1011,P1014,P1025

#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

struct num
{
    long num,x,y;
    long w,s,a,d;
}dot[250001l];


long dp[250001l];
long b[250001l];

void csort(long n)
{
    long c[50001l];
    long i;
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    for(i=1;i<=n;i++)
     c[dot[i].num]++;
    for(i=2;i<=50000;i++)
        c[i]+=c[i-1];
    for(i=1;i<=n;i++)
    {
        b[c[dot[i].num]]=i;
        c[dot[i].num]--;
    }
}

int main(int argc, char *argv[])
{
    long r,c,i,j;
    long n,mm=0;
    memset(dot,0,sizeof(dot));
    n=1;
    scanf("%d%d",&r,&c);
    for(i=1;i<=r;i++)
     for(j=1;j<=c;j++)
     {
            scanf("%d",&dot[n].num);
            dot[n].x=i;
            dot[n].y=j;
            if(i-1>=1)
            dot[n].w=n-c;else dot[n].w=-1;
            if(i+1<=r)
            dot[n].s=n+c;else dot[n].s=-1;
            if(j-1>=1)
            dot[n].a=n-1;else dot[n].a=-1;
            if(j+1<=c)
            dot[n].d=n+1;else dot[n].d=-1;
            n++;
     }
    n-=1;
    csort(n);
    memset(dp,0,sizeof(dp));
/*    for(i=1;i<=n;i++)
    {
        cout<<i<<' '<<dot[i].num<<'x'<<dot[i].x<<'y'<<dot[i].y<<'w';
        cout<<dot[i].w<<'s'<<dot[i].s<<'a'<<dot[i].a<<'d'<<dot[i].d<<endl;
    }*/
    for(i=n;i>=1;i--)
    {
        if(dot[b[i]].w!=-1)if(dp[dot[b[i]].w]<dp[b[i]]+1&&dot[dot[b[i]].w].num<dot[b[i]].num)dp[dot[b[i]].w]=dp[b[i]]+1;
        if(dp[dot[b[i]].w]>mm)mm=dp[dot[b[i]].w];
        if(dot[b[i]].s!=-1)if(dp[dot[b[i]].s]<dp[b[i]]+1&&dot[dot[b[i]].s].num<dot[b[i]].num)dp[dot[b[i]].s]=dp[b[i]]+1;
        if(dp[dot[b[i]].s]>mm)mm=dp[dot[b[i]].s];
        if(dot[b[i]].a!=-1)if(dp[dot[b[i]].a]<dp[b[i]]+1&&dot[dot[b[i]].a].num<dot[b[i]].num)dp[dot[b[i]].a]=dp[b[i]]+1;
        if(dp[dot[b[i]].a]>mm)mm=dp[dot[b[i]].a];
        if(dot[b[i]].d!=-1)if(dp[dot[b[i]].d]<dp[b[i]]+1&&dot[dot[b[i]].d].num<dot[b[i]].num)dp[dot[b[i]].d]=dp[b[i]]+1;
        if(dp[dot[b[i]].d]>mm)mm=dp[dot[b[i]].d];
        if(dp[b[i]]>mm)mm=dp[b[i]];
    }
    printf("%d\n",mm+1);
    system("pause");
    return 0;
}