洛谷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;
}