题目

BZOJ 传送门=￣ω￣=
LUOGU 传送门=￣ω￣=

题目描述

输入格式

输出格式

样例输入

4
1701 1702 1703 1704

样例输出

8

题解

基础区间 DP，要注意题意是前一个入队的人和当前的人比，不是队的右端和当前的人比……（窝就被坑了）。
所以我们设：$f[i,j,p]$(p=0 或 1) 为区间为 $[l,r]$，当前要把这个人插入到左端 (p=0) 或右端 (p=1) 时有多少种不同解。
然后 $arr[i]$表示第 i 个人的高度
所以可以得到这个递推式：
$f[i,j,0]=f[i,j-1,0]×(arr[j]>arr[i])+f[i,j-1,1]×(arr[j]>arr[j-1])$
$f[i,j,1]=f[i+1,j,0]×(arr[i]<arr[i+1])+f[i+1,j,1]×(arr[i]<arr[j])$

注意！$f[i,i,0]=1,f[i,i,1]=0$！或者 $f[i,i,1]=1,f[i,i,0]=0$也行！不然会重复计算！

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename tp>void read(tp & dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
typedef long long LL;
LL n,arr[1005],f[1005][1005][2];
bool book[1005][1005][2];
LL dfs(LL l,LL r,LL p)
{
    if(l==r)return p?1:0;
    if(book[l][r][p])return f[l][r][p];
    book[l][r][p]=1;
    if(p)
        f[l][r][p]+=dfs(l,r-1,0)*(arr[r]>arr[l]),
        f[l][r][p]+=dfs(l,r-1,1)*(arr[r]>arr[r-1]);
    else
        f[l][r][p]+=dfs(l+1,r,0)*(arr[l]<arr[l+1]),
        f[l][r][p]+=dfs(l+1,r,1)*(arr[l]<arr[r]);
    return f[l][r][p]%19650827;
}
int main()
{
    read(n);
    for(LL i=1;i<=n;read(arr[i++]));
    printf("%lld\n",(dfs(1,n,0)+dfs(1,n,1))%19650827);
    return 0;
}