题目链接

题解

区间dp

\(f[i][j]\)表示i~j区间最后一次插入的是\(a[i]\)

\(g[i][j]\)表示i~j区间最后一次插入的是\(a[j]\)

然后就是普通区间dp转移

Code

#include<bits/stdc++.h>
#define LL long long
#define RG register
inline int gi() {
bool f = 0; char c = getchar();
RG int x = 0;
while (c!='-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = 1, c = getchar();
while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();
return f ? -x:x;
}
using namespace std;
const int N = 1010, Mod = 19650827;
int a[N], f[N][N], g[N][N];
//f最后一次插在前面,g插在后面 int main() {
int n = gi();
for (int i = 1; i <= n; i++) a[i] = gi();
for (int i = 1; i <= n; i++)
f[i][i] = 1;
for (int len = 1; len < n; len++) {
for (int i = 1; i+len <= n; i++) {
int j = i+len;
f[i][j] = (f[i+1][j]*(a[i+1]>a[i]) + g[i+1][j]*(a[j]>a[i])) % Mod;
g[i][j] = (g[i][j-1]*(a[j]>a[j-1]) + f[i][j-1]*(a[i]<a[j])) % Mod;
}
}
printf("%d\n", (f[1][n]+g[1][n])%Mod);
return 0;
}
05-11 18:13
查看更多