区间DP

手动模拟一下,我们发现本题就是一个左右加数的区间DP

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

const int MAXN = 1005, MOD = 19650827;

int num[MAXN], dp[MAXN][MAXN][2], n;

int main() {

	cin >> n;

	for(int i = 1; i <= n; i++) cin >> num[i], dp[i][i][0] = 1;

	for(int k = 2; k <= n; k++) {

		for(int i = 1; i + k - 1 <= n; i++) {

			int j = i + k - 1;

			if(num[j] > num[j - 1]) dp[i][j][1] += dp[i][j - 1][1];

			if(num[j] > num[i]) dp[i][j][1] += dp[i][j - 1][0];

			if(num[i] < num[i + 1]) dp[i][j][0] += dp[i + 1][j][0];

			if(num[i] < num[j]) dp[i][j][0] += dp[i + 1][j][1];

			dp[i][j][1] %= MOD; dp[i][j][0] %= MOD;

		}

	}

	printf("%d\n", (dp[1][n][0] + dp[1][n][1]) % MOD);

	return 0;

}