题解 P3205 【[HNOI2010]CHORUS 合唱队】

· · 题解

设f[i][j]为可以排成理想队列中[i,j]区间，且以最后一个排进去是第i人的初始队列种数。

--- $f$数组情况： ①前一个排进去的人是$i+1$，当前人插到最左边，有： $f[i+1][j]\qquad\cdots\qquad(a[i]<a[i+1])

②前一个排进去的人是j，当前人插到最左边，有：

g[i+1][j]\qquad\cdots\qquad(a[i]<a[j])

根据加法原理，求和，即

f[i][i+len]=
    (f[i+1][i+len]*(a[i]<a[i+1])+g[i+1][i+len]*(a[i]<a[i+len]))%mod;
③前一个排进去的人是$i$，当前人插到最右边，有： $f[i][j-1]\qquad\cdots\qquad(a[i]>a[j])

④前一个排进去的人是j-1，当前人插到最右边，有：

g[i][j-1]\qquad\cdots\qquad(a[i]>a[j-1])

根据加法原理，求和，即：

g[i][i+len]=
    (f[i][i+len-1]*(a[i+len]>a[i])+g[i][i+len-1]*(a[i+len]>a[i+len-1]))%mod;

代码： (76ms / 9.62MB)

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005, mod = 19650827;

int n, a[MAXN];

int f[MAXN][MAXN], g[MAXN][MAXN];
int sovle()
{
    for(int i=0;i<n;i++)  //初始值，只有一个人的区间只有1种情况
        f[i][i]=1;
    for(int len=1;len<n;len++)  //最基础的区间dp
        for(int i=0;i+len<n;i++)
        {
            f[i][i+len]=( f[i+1][i+len]*(a[i]<a[i+1]) + 
                          g[i+1][i+len]*(a[i]<a[i+len]) )%mod;  //这部分上面已经说得很清楚了
            g[i][i+len]=( f[i][i+len-1]*(a[i+len]>a[i]) +
                          g[i][i+len-1]*(a[i+len]>a[i+len-1]) )%mod;
        }
    return (f[0][n-1]+g[0][n-1])%mod;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++)  //读入
        cin>>a[i];
    cout<<sovle()<<endl;
    return 0;
}