[dynamic planning] interval dp:p3205 Chorus

 

 

 

 

Code ： 

Be careful

1. Fill in the form from small range to large range ：

2. Take the mold after each addition

#include<iostream>
using namespace std; 
int n;
int a[1001];
int dp[1001][1001][2];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>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;
			dp[i][j][0]=(dp[i+1][j][0]*(a[i]<a[i+1])+dp[i+1][j][1]*(a[i]<a[j]))%19650827;
			dp[i][j][1]=(dp[i][j-1][1]*(a[j]>a[j-1])+dp[i][j-1][0]*(a[j]>a[i]))%19650827;
		}
	}
	cout<<(dp[1][n][1]+dp[1][n][0])%19650827;
	
}