洛谷P3205 [HNOI2010]合唱队题解

题目链接：P3205 [HNOI2010]合唱队

题意：

为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 $n$ 个人，第 $i$ 个人的身高为 $h_i$ 米（$1000 \le h_i \le 2000$），并已知任何两个人的身高都不同。假定最终排出的队形是 $A$ 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中：

第一个人直接插入空的当前队形中。

对从第二个人开始的每个人，如果他比前面那个人高（$h$ 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（$h$ 较小），那么将他插入当前队形的最左边。

当 $n$ 个人全部插入当前队形后便获得最终排出的队形。

例如，有 $6$ 个人站成一个初始队形，身高依次为 $1850, 1900, 1700, 1650, 1800, 1750$，
那么小 A 会按以下步骤获得最终排出的队形：

$1850$。

$1850, 1900$，因为 $1900 > 1850$。

$1700, 1850, 1900$，因为 $1700 < 1900$。

$1650, 1700, 1850, 1900$，因为 $1650 < 1700$。

$1650, 1700, 1850, 1900, 1800$，因为 $1800 > 1650$。

$1750, 1650, 1700, 1850, 1900, 1800$，因为 $1750 < 1800$。

因此，最终排出的队形是 $1750, 1650, 1700, 1850, 1900, 1800$。

小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。

请求出答案对 $19650827$ 取模的值。

容易发现方案数与区间的长度有关

并且一个区间的两侧都可以扩展

考虑使用区间dp

这个题看上去还挺乱的，所以我们抓住关键点

如果某一排列中， $b$ 比它前面的 $a$ 小，那么 $b$ 会从左边加入区间

而加入 $b$ 之前， $a$ 只有可能在区间的左端点或右端点

设 $dp[i][j][0/1]$ 表示区间 $[i,j]$ 的方案数，其中：

$0$ 表示 $a[i]$ 是本次转移中 从左侧 向区间内加入的数
$1$ 表示 $a[j]$ 是本次转移中 从右侧 向区间内加入的数

对于左侧加入的数，即 $a[i]$ ，它的前一个数要么是 $a[i+1]$ ，要么是 $a[j]$

对于右侧加入的数，即 $a[j]$ ，它的前一个数要么是 $a[j-1]$ ，要么是 $a[i]$

如果满足条件即可转移，如下

if(a[i]<a[i+1]) dp[i][j][0]+=dp[i+1][j][0];
if(a[i]<a[j]) dp[i][j][0]+=dp[i+1][j][1];
if(a[j]>a[j-1]) dp[i][j][1]+=dp[i][j-1][1];
if(a[j]>a[i]) dp[i][j][1]+=dp[i][j-1][0];
dp[i][j][0]%=p; dp[i][j][1]%=p;
dp[i][j][0]%=p; dp[i][j][1]%=p; // p=19650827

考虑边界 $i=j$ 时

此时认为它们都是左侧加入的即可（认为是右侧也可）

即 dp[i][i][0]=1，而不是dp[i][i][0]=dp[i][i][1]=1

为什么前者是正确的，而后者是错误的？

因为区间长度为 $2$ 时，有 $i+1=j$ 且 $j-1=i$

也就是后面的会多转移一次，根据乘法原理，最后答案会 $\times 2$

因此要去掉这个 $2$ （当然你可以去求个逆元啥的 qwq）

然后我们就可以 $O(n^2)$ 解决这个题目辣！

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1005)
const int p=19650827;
int n;
int a[N],dp[N][N][2];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) dp[i][i][0]=1;
    for(int len=2; len<=n; len++)
        for(int i=1,j=i+len-1; j<=n; i++,j++)
        {
            if(a[i]<a[i+1])dp[i][j][0]+=dp[i+1][j][0];
            if(a[i]<a[j])dp[i][j][0]+=dp[i+1][j][1];
            if(a[j]>a[j-1])dp[i][j][1]+=dp[i][j-1][1];
            if(a[j]>a[i])dp[i][j][1]+=dp[i][j-1][0];
            dp[i][j][0]%=p; dp[i][j][1]%=p;
        }
    cout << ((dp[1][n][0]+dp[1][n][1])%p) << endl;
    return 0;
}