P3205 [HNOI2010] 合唱队

题目

P3205 [HNOI2010] 合唱队

算法标签: 动态规划, 区间$dp$

思路

首先明确动态规划可以解决决策类型的问题, 因为每一步都是决策因此可以使用动态规划解决, 那么问题就变成为什么是区间$dp$?

因为每一步决策都会使当前区间变大, 也就是长度较长的区间是可以由长度较短的区间状态推出, 因为对于当前人来说可能插入到左侧也可能插入到右侧, 因此可以定义状态表示$f[i][j]$表示当前序列是$i$到$j$并且第$i$个人插入到左侧的所有方案, 同理定义$g[i][j]$是插入右侧的所有方案

既然状态表示有了就需要考虑如何进行状态转移也就是状态计算?
还是按照最后一步进行划分, $f[i][j]=f[i+1][j]+g[i+1][j]$, $g[i][j]$同理

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

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010, MOD = 19650827;int n, w[N];
int f[N][N], g[N][N];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i) cin >> w[i];for (int i = 1; i <= n; ++i) f[i][i] = 1;for (int len = 2; len <= n; ++len) {for (int i = 1; i + len - 1 <= n; ++i) {int j = i + len - 1;f[i][j] = (f[i + 1][j] * (w[i] < w[i + 1]) % MOD + g[i + 1][j] * (w[i] < w[j]) % MOD) % MOD;g[i][j] = (f[i][j - 1] * (w[j] > w[i]) % MOD + g[i][j - 1] * (w[j] > w[j - 1]) % MOD) % MOD;}}int ans = (f[1][n] + g[1][n]) % MOD;cout << ans << "\n";return 0;
}