『 Luogu P3205 』 HNOI2010 合唱队

解题思路

设置两个二维数组 $f$ 和 $g$，含义如下。

$f[l][r]$ 表示在期望得到的队形中 $l\rightarrow r$ 这段区间初始队形排列的方案数，并且最后一个加入进去的是第 $l$ 个人。

$g[l][r]$ 表示在期望得到的队形中 $l\rightarrow r$ 这段区间初始队形排列的方案数，并且最后一个加入进去的是第 $r$ 个人。

那么可以看出来 $g[l][r]$ 可以从 $g[l][r-1]$ 跟新出来，$f[l][r]$ 可以从 $f[l+1][r]$ 跟新出来。

大致可以分为下面四种情况：

现在决策的这个人插到队伍的最左边，即当前这个人比前一个加入队列的要矮，针对 $f[l][r]$ 前一个排进去的人是在第 $l+1$ 的位置上，$f[l+1][r]\rightarrow a[l]<a[l+1]$前一个排进去的人是在第 $r$ 的位置上，$g[l+1][r]\rightarrow a[l]<a[r]$现在决策的这个人插到队伍的最右边，即当前这个人比前一个加入队列的要高，针对 $g[l][r]$ 前一个排进去的人是在第 $l$ 的位置上，$f[l][r-1]\rightarrow a[r]>a[l]$前一个排进去的人是在第 $r-1$ 的位置上，$g[l][r-1]\rightarrow a[r]>a[r-1]$

根据上面的关系就可以写出状态转移方程

记得要初始化 $l=r$ 的数组，还有就是枚举区间长度的时候从 $2$ 开始枚举，否则会改变 之前初始化的数组造成答案出错

 

附上代码

#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn = 1003, HA = 19650827; int n, f[maxn][maxn], g[maxn][maxn], a[maxn]; int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &a[i]); for(int i=1; i<=n; i++) f[i][i] = 1; static int r; for(int i=2; i<=n; i++) { for(int l=1; l+i-1<=n; l++) { r = l+i-1; f[l][r] = f[l+1][r] * (a[l]<a[l+1]) % HA + g[l+1][r] * (a[l]<a[r]) % HA; f[l][r] = f[l][r] % HA; g[l][r] = f[l][r-1] * (a[r]>a[l]) % HA + g[l][r-1] * (a[r]>a[r-1]) % HA; g[l][r] = g[l][r] % HA; } } printf("%d", (g[1][n]+f[1][n]) % HA); }

 

转载于:https://www.cnblogs.com/bljfy/p/9572712.html

相关资源：数据结构—成绩单生成器