lg3205 发表于 2018-05-10 | 分类于 题解 | 阅读数 次 链接:lg3205 题解 DP[i][j][0/1]表示区间i~j,最后一个人站在左边或者右边可以推出的原始队形的种数 123456789101112131415161718192021222324252627#include<iostream>#include<cstdio>#include<cmath>#include<cstdlib>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e3+7;const int p=19650827;int dp[N][N][2],nm[N],n;int main(){ scanf("%d",&n); rep(i,1,n)dp[i][i][0]=1; rep(i,1,n)scanf("%d",&nm[i]); rep(l,2,n)rep(i,1,n-l+1){ int j=i+l-1; if(nm[j]>nm[j-1])dp[i][j][1]+=dp[i][j-1][1]; if(nm[j]>nm[i])dp[i][j][1]+=dp[i][j-1][0]; if(nm[i]<nm[i+1])dp[i][j][0]+=dp[i+1][j][0]; if(nm[i]<nm[j])dp[i][j][0]+=dp[i+1][j][1]; dp[i][j][0]%=p;dp[i][j][1]%=p; } printf("%d\n",(dp[1][n][0]+dp[1][n][1])%p); return 0;}