寒假最后一题补完啦 ^∀^
题意
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。
代码
代码语言：javascript复制#include<cstdio>
#include<cstring>
#define ll long long
#define N 75
int n,k;
ll dp[N][N],ans;
int b[N][N];
//b[i][j] -2 -1 3 1 2
//i s j > >= = <= <
int ch(int fl,int fr,int a,int c)//现在排的位置上的数要比自由部分的小
{
for(int i=fl; i<=fr; i )
if(b[a][i]==3||b[c][i]==3||b[a][i]<0||b[c][i]<0)return 0;
return 1;
}
int cc(int bl,int br,int a,int c){//现在排的位置上的数要比排好部分的大
for(int i=1;i<=bl;i )
if(b[a][i]>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;
}
