lg3205

发表于 | 分类于 | 阅读数 次

链接:lg3205

题解

  • DP[i][j][0/1]表示区间i~j,最后一个人站在左边或者右边可以推出的原始队形的种数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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 long
using 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;
}