【BZOJ1996】合唱队（动态规划）

时间：2023-03-08 20:08:07
【BZOJ1996】合唱队（动态规划）

【BZOJ1996】合唱队（动态规划）

题面

BZOJ

题解

很容易的一道题

因为每个人不是放在了左边就是放在了右边

所以每次放好的人必定是原序列的一个子串

所以，很容易想到区间\(dp\)

设\(f[i][j]\)表示已经放好了第\(i\)个人到第\(j\)个人的方案数

因为不知道这个人的前面是当前序列的左端还是右端

所以再加一维\([0/1]\)表示上一个放的人在左边还是右边

然后分类讨论一下大力转移即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 1200

#define MOD 19650827

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int f[MAX][MAX][2];

int n,a[MAX];

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=read(),f[i][i][0]=1;

	for(int len=2;len<=n;++len)

	{

		for(int i=1;i+len-1<=n;++i)

		{

			int j=i+len-1;

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

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

			if(a[j]>a[i])f[i][j][1]=(f[i][j][1]+f[i][j-1][0])%MOD;

			if(a[j]>a[j-1])f[i][j][1]=(f[i][j][1]+f[i][j-1][1])%MOD;

		}

	}

	printf("%d\n",(f[1][n][0]+f[1][n][1])%MOD);

	return 0;

}

相关文章