寒假最后一补完啦 ^∀^

题意

1到n每个数字有两个，排成先不降后不升的序列，比如112332，并且满足k个形如 3 <= 6 代表第三个数字要≤第六个数字这样的约束要求，求有多少种排法。

分析

区间DP，dp[i][j]表示只有区间[i,j]还没填时的方案数。

b[i][j]表示第i和j位置的数字约束关系。

然后从两头开始排，每次把两个数字t放在两边或者同一边。

dp[i+1][j-1]+=dp[i][j];//放在两边

dp[i+2][j]+=dp[i][j];//放在左边

dp[i][j-2]+=dp[i][j];//放在右边

并且要满足约束条件。如果i位置小于j位置，那么必须先放i位置。

即放在当前位置上的数>(≥)已经放好的位置上的数，<(≤)未放置的位置上的数。

并且每次放的两个位置如果有约束关系，只能是含有=的（=、≥、≤）。

当j==i+1时，就只能一种放法了，这时候就可以累加答案了。

当我们放数字t时，区间[i,j]的长度是2*n-2*(t-1)，所以j=i+2*n-2*(t-1)-1=2*n-2*t+i+1。

方案数比较大，所以要用long long。

代码

#include
     
      #include
      
       #define ll long long#define N 75int n,k;ll dp[N][N],ans;int b[N][N];//b[i][j] -2   -1   3   1   2//i s j   >    >=   =   <=  
       
        0||b[c][i]>0)return 0;    for(int i=br;i<=2*n;i++)        if(b[a][i]>0||b[c][i]>0)return 0;    return 1;}int check(int i,int j)//不可以放在两个数字不允许相同的位置上{    return b[i][j]!=-2&&b[i][j]!=2;}int main(){    scanf("%d%d",&n,&k);    for(int i=1; i<=k; i++)    {        int l,r,f=3;        char s[5];        scanf("%d%s%d",&l,s,&r);        if(s[0]=='<')        {            f=2;            if(s[1])f--;        }        else if(s[0]=='>')        {            f=-2;            if(s[1])f++;        }        b[l][r]=f;        b[r][l]=f==3?f:-f;    }    dp[1][2*n]=1;    for(int t=1; t<=n; t++)        for(int i=1; i<=2*t-1; i++)        {            int j=2*n-2*t+i+1;            if(dp[i][j])            {                if(j==i+1)                {                    if(check(i,j))                        ans+=dp[i][j];                }                else                {                    if(ch(i+1,j-1,i,j)&&cc(i-1,j+1,i,j)&&check(i,j))                        dp[i+1][j-1]+=dp[i][j];                    if(ch(i+2,j,i,i+1)&&cc(i-1,j+1,i,i+1)&&check(i,i+1))                        dp[i+2][j]+=dp[i][j];                    if(ch(i,j-2,j-1,j)&&cc(i-1,j+1,j-1,j)&&check(j-1,j))                        dp[i][j-2]+=dp[i][j];                }            }        }    printf("%lld",ans);    return 0;}