题面:https://www.luogu.org/problemnew/show/P3205
本题中可以设数组f是当本次选择队首元素时一共有多少种原序列
数组g是当本次选择队尾元素时一共有多少种原序列
那么就有了
if(a[i]<=a[i+1])
f[i][j]=(f[i][j]+f[i+1][j])%MOD;
if(a[i]<a[j]){
f[i][j]=(f[i][j]+g[i][j-1])%MOD;
g[i][j]=(g[i][j]+f[i-1][j])%MOD;
}
if(a[j]>a[j-1])
g[i][j]=(g[i][j]+g[i][j-1])%MOD;
Code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1010
#define MOD 19650827
using namespace std;
int n;
int a[N];
int f[N][N];
int g[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[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(a[i]<a[i+1])
f[i][j]=(f[i][j]+f[i+1][j])%MOD;
if(a[i]<a[j])
f[i][j]=(f[i][j]+g[i+1][j])%MOD;
if(a[i]<a[j])
g[i][j]=(g[i][j]+f[i][j-1])%MOD;
if(a[j]>a[j-1])
g[i][j]=(g[i][j]+g[i][j-1])%MOD;
}
}
printf("%d\n",(f[1][n]+g[1][n])%MOD);
return 0;
}