自动搬运

查看原文

来自洛谷，原作者为

	kradcigam 永不放弃之心，将成为贯穿逆境之光！

搬运于2025-08-24 21:46:28，当前版本为作者最后更新于2019-08-28 11:58:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

讲讲我的做法

看了题目发现要用区间 dp，为什么?

我们发现区间 dp 有一个性质——大区间包含小区间，这道题就符合这样的一个性质:

所以我们要用区间 dp 来解决这道题。

如何设计状态

那么我们要怎么设计状态，我们想，每给人进入队伍里，只有 2 种可能：

1. 从左边加入;

2. 从右边进入。

所以我们的状态是有3个数：

$f_{i,j,0}$ 表示的是第 $i$ 人从左边进来的方案数；

$f_{i,j,1}$ 表示的是第 $j$ 人从右边进来的方案数。

推导状态转移方程

从左边进来肯定前 $1$ 个人比他高，前 $1$ 个人有 $2$ 种情况，要么在 $i+1$ 号位置，要么在 $j$ 号位置。

同理，

从右边进来肯定前 $1$ 个人比他矮，前 $1$ 个人有 $2$ 种情况，要么在 $j-1$ 号位置，要么在 $i$ 号位置。

那么状态转移方程就出来了：

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

边界条件

当 $i=j$ 的时候显然只有一种方案，所以边界条件是：

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

然而你会发现你 WA 了，为什么？

因为，只有一个人的时候方案只有 $1$ 种，可是我们这里却有 $2$ 种方案，所以我们得默认 $1$ 个人的时候，是从左边进来，于是我们就有了正确的边界条件：

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

完整代码

#include <bits/stdc++.h>
using namespace std;
int f[2010][2010][2],a[2010];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)f[i][i][0]=1;
	for(int len=1;len<=n;len++)
		for(int i=1,j=i+len;j<=n;i++,j++){
			if(a[i]<a[i+1])f[i][j][0]+=f[i+1][j][0];
			if(a[i]<a[j])f[i][j][0]+=f[i+1][j][1];
			if(a[j]>a[i])f[i][j][1]+=f[i][j-1][0];
			if(a[j]>a[j-1])f[i][j][1]+=f[i][j-1][1];
			f[i][j][0]%=19650827;
			f[i][j][1]%=19650827;
		}
	cout<<(f[1][n][0]+f[1][n][1])%19650827;
	return 0;
}