Luogu 3205 [HNOI2010]合唱队

初赛滚粗的我含着眼泪写代码……

设$f_{l, r, 0/1}$表示$[l, r]$的区间的队伍排列好，且最后一个插进去的在左边$(0)$/右边$(1)$的方案数，那么有初态$f_{i, i, 0} = 1$。

转移的时候只要对比一下左边的数和右边的数和最后一个插入的数的大小关系就可以确定转移到$0/1$了。

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

Code：

#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1005;
const int P = 19650827;

int n, a[N], f[N][N][2];

inline void read(int &X) {
    X = 0; char ch = 0; int op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
} 

inline void inc(int &x, int y) {
    x += y;
    if(x >= P) x -= P;
}

int main() {
    read(n);
    for(int i = 1; i <= n; ++i) {
        read(a[i]);
        f[i][i][0] = 1;//f[i][i][1] = 1;
    }
    
    for(int len = 1; len < n; ++len) {
        for(int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            if(r + 1 <= n) {
                if(a[r + 1] > a[l]) inc(f[l][r + 1][1], f[l][r][0]);
                if(a[r + 1] > a[r]) inc(f[l][r + 1][1], f[l][r][1]);
            }
            if(l - 1 >= 1) {
                if(a[l - 1] < a[l]) inc(f[l - 1][r][0], f[l][r][0]);
                if(a[l - 1] < a[r]) inc(f[l - 1][r][0], f[l][r][1]);
            }
        }
    }
    
    int ans = f[1][n][0] + f[1][n][1];
    if(ans >= P) ans -= P;
    
    printf("%d
", ans);
    return 0;
}