url: https://www.luogu.com.cn/problem/P3205
tag:
动态规划，区间DP，2010
思路：
利用区间DP来做。设 f[i][j][0] 表示区间i到j中i从左边进入区间的情况， f[i][j][1] 表示区间i到j中j从右边进入区间的情况。当i从左边进去时，上一个区间应该是 i + 1 到 j ，所以只有当 h[i] < h[i + 1] 以及 h[i] < h[j] 时才能更新。同理当 h[j] > h[i] 以及 h[j] > h[j - 1] 时，j从右边进入区间，区间从 i 到 j - 1 更新到 i 到 j 。初始化为了避免当一个数字时有两种情况，所以可以是都假装是从左边进入区间，（或者是右边也行只要保证只保留一种情况就行）。最后答案将 f[1][n][0] 和 f[1][n][1] 两种情况相加后取模输出即可。
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010, mod = 19650827;
typedef long long LL;
int n;
int h[N];
LL f[N][N][2];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> h[i];
for (int i = 1; i <= n; i ++) f[i][i][0] = 1;
for (int len = 1; len <= n; len ++)
{
for (int i = 1, j = i + len; j <= n; i ++, j ++)
{
if (h[i] < h[i + 1]) f[i][j][0] += f[i + 1][j][0];
if (h[i] < h[j]) f[i][j][0] += f[i + 1][j][1];
if (h[j] > h[i]) f[i][j][1] += f[i][j - 1][0];
if (h[j] > h[j - 1]) f[i][j][1] += f[i][j - 1][1];
f[i][j][0] %= mod;
f[i][j][1] %= mod;
}
}
LL res = (f[1][n][0] + f[1][n][1]) % mod;
cout << res << endl;
return 0;
}