Luogu P3205 [HNOI2010]合唱队

题目描述

https://www.luogu.com.cn/problem/P3205

Solution

由题意可知，理想队形中的一段区间对应原队列的一段前缀

我们令f[i][j][0/1]表示理想队形中[i,j]的数已经分配完毕，0/1表示上一个选的数是i还是j

转移时向左右拓展一位即可

换一个角度从原数列考虑，每次左右拓展就是在末尾添加一个数，0/1记录的是上一位选的数是什么

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

#include <iostream>
#include <cstdio>
#define maxn 1010
using namespace std;

int n, a[maxn]; 

const int p = 19650827;

inline void add(int &x, int y) { x = (x + y) % p; } 

int f[maxn][maxn][2]; 

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) f[i][i][0] = 1;
    for (int l = 1; l < n; ++l)
        for (int i = 1; i + l - 1 <= n; ++i) {
            int j = i + l - 1;
            if (i && a[i - 1] < a[i]) add(f[i - 1][j][0], f[i][j][0]);
            if (i && a[i - 1] < a[j]) add(f[i - 1][j][0], f[i][j][1]);
            if (j < n && a[j + 1] > a[i]) add(f[i][j + 1][1], f[i][j][0]);
            if (j < n && a[j + 1] > a[j]) add(f[i][j + 1][1], f[i][j][1]);
        }
    cout << (f[1][n][0] + f[1][n][1]) % p << endl; 
    return 0;
}