关键
构造一个先上升,后下降的全排列
采用区间dp f(i,j)表示i到j合法的方案有多少种
从打的开始填写,就可以保证一定是对的
然后特殊的位置check一下就行了
很久没有写过区间dp了,很奇妙
代码
#include <bits/stdc++.h>
using namespace std;
const int M=105,mod=1e9+7;
int f[M][M];
int n,a,b,x,y;
bool check(int i,int v) {
if(i==a)return v==x;
if(i==b)return y==v;
return 1;
}
void add(int &x,int y) {
x=(x+y)%mod;
}
//区间dp,这个想法很好
//也就看中间的就行了
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int TT;cin>>TT;
while(TT--) {
memset(f,0,sizeof(f));
cin>>n>>a>>b>>x>>y;
for(int i=2;i<n;i++)
if(check(i,n))f[i][i]=1;
for(int len=2;len<=n;len++)
for(int l=1,r=l+len-1;r<=n;l++,r++) {
if(check(l,n-len+1))add(f[l][r],f[l+1][r]);
if(check(r,n-len+1))add(f[l][r],f[l][r-1]);
}
cout<<f[1][n]<<endl;
}
return 0;
}
标签:return,840,--,TT,CF,cin,int,dp
From: https://www.cnblogs.com/basicecho/p/17012197.html