题目描述
输入
输出
样例输入
4
1701 1702 1703 1704
样例输出
8
题解
区间dp。设 dp[ i ][ j ][ 1/0 ] 为满足a[ i ] 到 a[ j ]最后加进的元素在最左边(0)或最右边(1)的满足初始队形的方案数，那么分两种情况：
1. dp[ i ][ j ][ 0 ] 的转移，如果最后加入的a[ i ] 比 a[ i+1 ]小，那么dp[ i ][ j ][ 0 ] + = dp[ i+1 ][ j ][ 0 ]；如果 a[ i ] 比 a[ j ] 小，那么 dp[ i ][ j ][ 0 ] + = dp[ i+1 ][ j ][ 1 ]
2. dp[ i ][ j ][ 1 ] 的转移，与商贸一样，如果 a[ j ] > a[ j-1 ] ， dp[ i ][ j ][ 1 ] + = dp[ i ][ j-1 ][ 1 ] ；如果 a[ j ] > a[ i ] ， dp[ i ][ j ][ 1 ] + = dp[ i ][ j-1 ][ 0 ]
边界：当区间只有一个数的时候，只有一种方案，我们默认是从左边放入的，即： dp[ i ][ i ][ 0 ] = 1 ， dp[ i ][ i ][ 1 ] = 0。
然后区间dp。
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn=1000+50; const int mod=19650827; int dp[maxn][maxn][2],n,a[maxn]; template<typename T>void read(T& aa){ char cc; ll ff;aa=0;cc=getchar();ff=1; while((cc<'0'||cc>'9')&&cc!='-') cc=getchar(); if(cc=='-') ff=-1,cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); aa*=ff; } int main(){ read(n); for(int i=1;i<=n;i++) read(a[i]),dp[i][i][0]=1; for(int len=2;len<=n;len++) for(int i=1;i+len-1<=n;i++){ int j=i+len-1; if(a[i]<a[i+1]) dp[i][j][0]+=dp[i+1][j][0]; if(a[i]<a[j]) dp[i][j][0]+=dp[i+1][j][1]; dp[i][j][0]%=mod; if(a[j]>a[j-1]) dp[i][j][1]+=dp[i][j-1][1]; if(a[j]>a[i]) dp[i][j][1]+=dp[i][j-1][0]; dp[i][j][1]%=mod; } cout<<(dp[1][n][1]+dp[1][n][0])%mod; return 0; }