这是一道DP题T_T

https://www.luogu.org/problem/P3205

方程

• $f[i][j]$表示可以排成理想队形中的$[i, j]$, 且最后一个加进去的人被放在最左边。

• $g[i][j]$表示可以排成理想队形中的$[i, j]$, 且最后一个加进去的人被放在最右边。

• 对于$f[i][j]$，最后一个人被放在了$i$所以转移应在区间$[i + 1, j]$处。

• 对于$g[i][j]$，最后一个人被放在了$j$所以转移应在区间$[i, j - 1]$处。

所以:

• $f[i][j]$要在$f[i + 1][j]$和$g[i + 1][j]$转移过来
• $g[i][j]$要在$f[i][j - 1]$和$g[i][j - 1]$转移过来

考虑当什么时候f[i][j]会在f[i + 1][j]转移过来，
$f[i][j]$表示最后一个人放在了最左边，根据题目，最后一个人要比前面那个人矮才能放在最左边。

对于$f[i + 1][j]$来说，上一个人是$i + 1$，所以第$i$个人要矮于第$i + 1$个人，$f[i][j]$才能从$f[i + 1][j]$转移。

同理，当所以第$i$个人要矮于第$j$个人,$f[i][j]$才能从$g[i + 1][j]$转移过来。

$$f[L][R] = (f[L + 1][R] * (A[L + 1] > A[L]) + g[L + 1][R] * (A[R] > A[L]))$$

下面对于$g[i][j]$的转移同理，唯一的不同就是最后一个人被放在了最右边。

$$g[L][R] = (f[L][R - 1] * (A[L] < A[R]) + g[L][R - 1] * (A[R - 1] < A[R]))$$

区间DP，每个状态在转移时依赖于小区间的值，所以要保证短区间要早于长区间的处理时间。

我觉得这个题的意义还没有完成，我们从头思考，为什么要设计两个不同且相似的数组存储不同的状态。

对从第二个人开始的每个人，如果他比前面那个人高(H较大)，那么将他插入当前队形的最右边。如果他比前面那个人矮(H较小)，那么将他插入当前队形的最左边

每次决策和最后一次放进去人和当前人的高度关系有关，所以，我们在存储和转移状态时，必须知道最后一次是那个人被放进去了。所以我们就需要两个数组g,f来记录。

哦对了~借鉴了上一篇题解才写出来，谢谢上一位同学QAQ，我再记录一下自己的心路历程

/*!
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool written by Shu_Yu_Mo.
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#define _R register
#define inf 0x7fffffff
using namespace std;
const int _ = 1100;
const int MOD = 19650827;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); }
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
int n;
int A[_];
int f[_][_];//最后一个人放在最左边边 
int g[_][_];//最后一个人放在最右边边
int main()
{
    n = read();
    for(_R int i = 1;i <= n;i++){
        A[i] = read();
    }
    for(_R int i = 1;i <= n;i++)
        f[i][i] = 1;
    for(_R int len = 2;len <= n;len++){
        for(_R int L = 1;L + len - 1 <= n;L++){
            int R = L + len - 1;
            f[L][R] = (f[L + 1][R] * (A[L + 1] > A[L]) + g[L + 1][R] * (A[R] > A[L])) % MOD;
            g[L][R] = (f[L][R - 1] * (A[L] < A[R]) + g[L][R - 1] * (A[R - 1] < A[R])) % MOD;
        }
    }
    printf("%d", (f[1][n] + g[1][n]) % MOD);
    return 0;
}

UDP：@lzzhhh发现一处笔误……