「HNOI 2010」合唱队

Posted on | In

题目大意：

#include <cstdio>
 
const int N = 1005, mod = 19650827;
int n, a[N], f[N][N][2]; //f[l][r][0]表示区间[l,r]最后入队的是l
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), f[i][i][0] = 1;
    for (int k = 1; k < n; ++k) { //区间长度
        for (int l = 1, r = l + k; r <= n; ++l, r = l + k) {
            if (a[l] < a[l+1]) (f[l][r][0] += f[l+1][r][0]) %= mod;
            if (a[l] < a[r]) (f[l][r][0] += f[l+1][r][1]) %= mod;
            if (a[r] > a[r-1]) (f[l][r][1] += f[l][r-1][1]) %= mod;
            if (a[r] > a[l]) (f[l][r][1] += f[l][r-1][0]) %= mod;
        }
    }
    printf("%d\n", (f[1][n][0] + f[1][n][1]) % mod);
    return 0;
}

时间复杂度 $O(n^2)$