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

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

复习区间DPing

思路

把理想队列拆分成

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

样例：1701 1702 1703 1704

把1701拿出来求1702 1703 1704的理想队列
把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=;i<=n;i++)

        cin>>q[i];

    for(int i=;i<=n;i++)

        f[i][i]=;//初始化本身为一种

    for(int i=n-;i>=;i--)

        for(int j=i+;j<=n;j++)

        {

            if(q[i]<q[i+])//i+1是从队首取的所以+f[i+1][j]

                f[i][j]=(f[i][j]+f[i+][j])%MOD;

            if(q[i]<q[j])//j是从队尾取的所以+g[i+1][j]

                f[i][j]=(f[i][j]+g[i+][j])%MOD;

            if(q[i]<q[j])//i是从队首取的所以+f[i][j-1]

                g[i][j]=(g[i][j]+f[i][j-])%MOD;

            if(q[j-]<q[j])//j-1是从队尾取的所以+g[i][j-1]

                g[i][j]=(g[i][j]+g[i][j-])%MOD;

        }

    printf("%d",(f[][n]+g[][n])%MOD);

}

巴特西

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

思路

代码

最新文章

热门文章