P3205 [HNOI2010]合唱队 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题 大区间包括小区间，每加一个人都会让区间更大；
考虑区间DP：
对于区间 [ i ~ j ] ，这段区间最新进的人只有两种可能 i 或 j
所以我们定义：
f[i][j]最后一个加的人是 i ，组成区间[ i ~ j ]的方案数
g[i][j]最后一个加的人是 j ，组成区间[ i ~ j ]的方案数
对于 f [i][j] 的转移：
f[ i ][ j ]是由区间[ i+1~j ]转移过来的,且a[i] 是要小于上一个加入的大小
对于区间[ i+1 ~ j ]同理也是有两种可能 (i+1)是这段区间最后一个加入的 或 j是这段区间最后一个加入的
如果 (i+1)是区间[i+1,j]最后一个加入的,且为了让 i 是最后一个加入的，要满足(a[i+1]>a[i])则有转移方程 f[i][j]+=f[i+1][j];
如果 (j)是区间[i+1,j]最后一个加入的,且为了让 i 是最后一个加入的，要满足(a[j]>a[i])则有转移方程 f[i][j]+=g[i+1][j];
对于 g [i][j] 的转移：
g[ i ][ j ]是由区间[ i~j-1 ]转移过来的，且a[j]是大于上一个加入的大小
对于区间[ i ~ j-1 ]同理也是有两种可能 i 是这段区间最后一个加入的 或 j-1 是这段区间最后一个加入的
如果 i 是区间[i,j-1]最后一个加入的,且为了让 j 是最后一个加入的，要满足(a[j]>a[i])则有转移方程 g[i][j]+=f[i][j-1];
如果 j-1 是区间[i,j-1]最后一个加入的,且为了让 j 是最后一个加入的，要满足(a[j]>a[j-1])则有转移方程 g[i][j]+=g[i][j-1];
对于初始化状态：
for(int i=1;i<=n;i++) f[i][i]=1;初始化状态不能有g[i][i]=1，（n=1的情况就能推翻，可根据常理来想） Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define popb pop_back
#define fi first
#define se second
const int N=1e3+10;
const int MOD=19650827;
//const int inf=0x3f3f3f3f;
//const ll INF=0x3ffffffffffff;
int T,n,a[N],f[N][N],g[N][N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int main()
{
// freopen("","r",stdin);
// freopen("","w",stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) f[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
f[i][j]=(f[i+1][j]*(a[i+1]>a[i])+g[i+1][j]*(a[j]>a[i]))%MOD;
g[i][j]=(f[i][j-1]*(a[j]>a[i])+g[i][j-1]*(a[j]>a[j-1]))%MOD;
}
printf("%d",(f[1][n]+g[1][n])%MOD);
return 0;
}