51Nod 1522 上下序列 —— 区间DP

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1522

区间DP，从大往小加；

新加入一种数有3种加法：全加左边，全加右边，一左一右；

然后判断一下加完是否满足那些条件即可；

但判断这个条件还挺复杂，一不小心就写丑了错了...

冗余错误写法：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int n,m,c[][];

ll f[][][];

char ch[];

bool ck(int a,int b,int fl)

{

    if(fl==)

    {

        for(int i=,x,y;i<=m;i++)

        {

            x=c[i][]; y=c[i][];

            if((x==a&&y==b)||(x==b&&y==a)&&c[i][]!=)return ;

            if((x==a||x==b)&&y>b&&(c[i][]!=&&c[i][]!=))return ;

            if((y==a||y==b)&&x>b&&(c[i][]!=&&c[i][]!=))return ;

        }

        return ;

    }

    if(fl==)

    {

        for(int i=,x,y;i<=m;i++)

        {

            x=c[i][]; y=c[i][];

            if((x==a&&y==b)||(x==b&&y==a)&&c[i][]!=)return ;

            if((x==a||x==b)&&y<a&&(c[i][]!=&&c[i][]!=))return ;

            if((y==a||y==b)&&x<a&&(c[i][]!=&&c[i][]!=))return ;

        }

        return ;

    }

    if(fl==)

    {

        for(int i=,x,y;i<=m;i++)

        {

            x=c[i][]; y=c[i][];

            if((x==a&&y==b)||(x==b&&y==a)&&c[i][]!=)return ;

            if((x==a||x==b)&&(y>a&&y<b)&&(c[i][]!=&&c[i][]!=))return ;

            if((y==a||y==b)&&(x>a&&x<b)&&(c[i][]!=&&c[i][]!=))return ;

        }

        return ;

    }

    if(fl==)

    {

        for(int i=,x=c[i][],y=c[i][];i<=m;i++,x=c[i][],y=c[i][])

            if((x==a&&y==b)||(x==b&&y==a)&&(c[i][]==||c[i][]==))return ;

        return ;

    }

}

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        scanf("%d %s %d",&c[i][],&ch,&c[i][]);

        if(ch[]=='=')c[i][]=;

        else if(ch[]=='<'&&ch[]=='=')c[i][]=;

        else if(ch[]=='>'&&ch[]=='=')c[i][]=;

        else if(ch[]=='<')c[i][]=;

        else if(ch[]=='>')c[i][]=;

    }

    for(int i=;i<*n;i++)if(ck(i,i+,))f[n][i][i+]=;

    for(int i=n-;i;i--)

        for(int l=;l<=*n;l++)

            for(int r=l+;r<=*n;r++)

                if(f[i+][l][r])

                {

//                    printf("i=%d l=%d r=%d\n",i,l,r);

                    int x,y;

                    if(l>)

                    {

                        x=l-,y=l-;

                        if(ck(x,y,))f[i][x][r]+=f[i+][l][r];

//                                         printf("f[%d][%d][%d]=%d\n",i,x,r,f[i][x][r]);

                    }

                    if(r+<=*n)

                    {

                        x=r+,y=r+;

                        if(ck(x,y,))f[i][l][y]+=f[i+][l][r];

//                                         printf("f[%d][%d][%d]=%d\n",i,l,y,f[i][l][y]);

                    }

                    if(l>&&r+<=*n)

                    {

                        x=l-; y=r+;

                        if(ck(x,y,))f[i][x][y]+=f[i+][l][r];

//                                         printf("f[%d][%d][%d]=%d\n",i,x,y,f[i][x][y]);

                       }

                }

    printf("%lld\n",f[][][n<<]);

    return ;

}

囧

于是参考了一下TJ...

调了一小时只因把 x==b 写成 y==b ？！而且还一直没仔细看...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int n,m,c[][];

ll f[][];

char ch[];

bool ck0(int a,int b)

{

    for(int i=,x=c[i][],y=c[i][];i<=m;i++,x=c[i][],y=c[i][])

        if(((x==a&&y==b)||(x==b&&y==a))&&(c[i][]==||c[i][]==))return ;

    return ;

}

bool ck(int l,int r,int a,int b)

{

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

    {

        int x=c[i][],y=c[i][],cc=c[i][];

        bool ix=(x==a||x==b),iy=(y==a||y==b);

        bool kx=(x>=l&&x<=r),ky=(y>=l&&y<=r);

        if(cc==&&((ix!=iy)||(kx!=ky)))return ;//=

        if(cc==&&(!ky&&(ix||kx)))return ;//<

        if(cc==&&(!kx&&(iy||ky)))return ;//>

        if(cc==&&((ix&&!iy&&!ky)||(kx&&!ky)))return ;//<=

        if(cc==&&((iy&&!ix&&!kx)||(ky&&!kx)))return ;//>=

    }

    return ;

}

int main()

{

    scanf("%d%d",&n,&m);

    bool flag=; int cnt=;

    for(int i=,x,y,cc;i<=m;i++)

    {

        scanf("%d %s %d",&x,&ch,&y);

        if(ch[]=='=')cc=;

        else if(ch[]=='<'&&ch[]=='=')cc=;

        else if(ch[]=='>'&&ch[]=='=')cc=;

        else if(ch[]=='<')cc=;

        else if(ch[]=='>')cc=;

        if(x==y)

        {

            if(cc==||cc==)flag=;

            continue;//!

        }

        c[++cnt][]=x; c[cnt][]=y; c[cnt][]=cc;

    }

    if(flag){printf("0\n"); return ;}

    m=cnt;

    for(int i=;i<*n;i++)if(ck0(i,i+))f[i][i+]=;

    for(int l=;l<=*n;l+=)

        for(int i=;i<=*n-l+;i++)

        {

            int j=i+l-;

            if(ck(i+,j,i,i+))f[i][j]+=f[i+][j];

            if(ck(i,j-,j-,j))f[i][j]+=f[i][j-];

            if(ck(i+,j-,i,j))f[i][j]+=f[i+][j-];

        }

    printf("%lld\n",f[][*n]);

    return ;

}