【题解】洛谷P3205【HNOI2010】合唱队

洛谷 P3205：https://www.luogu.org/problemnew/show/P3205

复习区间DPing

思路

把理想队列拆分成

1. 第一个和后面几个 划分成求后面几个的理想队列
2. 最后一个和前面几个 划分成求前面几个的理想队列

        样例：1701 1702 1703 1704

1. 把1701拿出来 求1702 1703 1704的理想队列
2. 把1704拿出来 求1701 1702 1703的理想队列

因此需要两个数组来划分阶段

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

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

就可以得出数组f的两种情况：

前一个排进去的人是i+1 当前人插到最左边

if(q[i]<q[i+1])
f[i][j]=(f[i][j]+f[i+1][j])%MOD;

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

if(q[i]<q[j])
f[i][j]=(f[i][j]+g[i+1][j])%MOD;

同理可得数组g的两种情况：

前一个排进去的人是i 当前人插到最右边

if(q[i]<q[j])
g[i][j]=(g[i][j]+f[i][j-1])%MOD;

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

if(q[j-1]<q[j])
g[i][j]=(g[i][j]+g[i][j-1])%MOD;

答案存在f[1][n]+g[1][n]中

代码

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 1010
#define MOD 19650827
int n;
int q[maxn];
int f[maxn][maxn],g[maxn][maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        cin>>q[i];
    for(int i=1;i<=n;i++)
        f[i][i]=1;//初始化本身为一种 
    for(int i=n-1;i>=1;i--)
        for(int j=i+1;j<=n;j++)
        {
            if(q[i]<q[i+1])//i+1是从队首取的所以+f[i+1][j]
                f[i][j]=(f[i][j]+f[i+1][j])%MOD; 
            if(q[i]<q[j])//j是从队尾取的所以+g[i+1][j]
                f[i][j]=(f[i][j]+g[i+1][j])%MOD;
            if(q[i]<q[j])//i是从队首取的所以+f[i][j-1]
                g[i][j]=(g[i][j]+f[i][j-1])%MOD;
            if(q[j-1]<q[j])//j-1是从队尾取的所以+g[i][j-1]
                g[i][j]=(g[i][j]+g[i][j-1])%MOD;
        }
    printf("%d",(f[1][n]+g[1][n])%MOD);
}