Description

给定一个长度为 $n$ 的序列 $\{a_i\}$，可以选择一个子序列将其反转，求能获得的最大不下降子序列。

$n\leq 50$。

Solution

观察一下反转的性质，实际上就相当于将这个子序列两边对调，且不会有交错和并列，与区间 DP 能很好地搭配——选择反转两个数，他们之间的区间可以接着反转。

那么考虑 $f_{i,j}$ 表示区间 $[i,j]$ 的答案，其中只考虑是否反转 $a_i,a_j$。

考虑如何由小区间得到大区间的解，回忆 LIS 的 $O(n^2)$ 做法，与值有关，那么再加两维状态：$f_{i,j,l,r}$ 表示区间 $[i,j]$，值域 $[l,r]$ 的答案。

那么就可以方便的转移了。

首先，大值域显然可以由小值域得来，即 $f_{i,j,l,r}=\max(f_{i,j,l+1,r},f_{i,j,l,r-1})$。

为表述方便，记 $[\text{bool}]=\begin{cases}1&\text{if bool = TRUE} \\ 0&\text{if bool = FALSE}\end{cases}$​​。

当不反转 $a_i$​​，$a_j$​​ 时，$f_{i,j,l,r}=\max(f_{i+1,j,l,r}+[a_i=l],f_{i,j-1,l,r}+[a_j=r])$​​。

当反转 $a_i$，$a_j$ 时，$f_{i,j,l,r}=f_{i+1,j-1,l,r}+[a_i=l]+[a_j=r]$。

把上面的方程都取个 $\text{max}$，就得到这个状态的答案了。

初始状态就把区间长度为 $1$ 的合法状态都设成 $1$ 即可。

一开始把不相等的情况也考虑进去了，后来发现是错的：不相等的情况在值域扩张的时候会被考虑到，没必要再进行讨论。（其实把细节稍微改一下也能做）

Code

#include <algorithm>
#include <cstdio>
#include <iostream>

const int maxn = 55;

int a[maxn], b[maxn];
int f[maxn][maxn][maxn][maxn];

int n;

inline void upd_max(int &a, int b) { a = std::max(a, b); }
inline int change(bool x) { return x ? 1 : 0; }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];
    
    std::sort(b + 1, b + 1 + n);
    int tot = std::unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++)
        a[i] = std::lower_bound(b + 1, b + 1 + tot, a[i]) - b;
    // 其实没必要离散化。
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= a[i]; j++)
            for (int k = a[i]; k <= tot; k++)
                f[i][i][j][k] = 1;
    // DP的顺序需要考虑一下
    for (int len = 2; len <= n; len++)
    {
        for (int i = 1; i <= n; i++)
        {
            int j = i + len - 1;
            if (j > n)
                continue;
            for (int len2 = 1; len2 <= tot; len2++)
            {
                for (int l = 1; l <= tot; l++)
                {
                    int r = l + len2 - 1;
                    if (r > tot)
                        continue;
                    if (l != tot)
                        upd_max(f[i][j][l][r], f[i][j][l + 1][r]);
                    upd_max(f[i][j][l][r], f[i][j][l][r - 1]);
                    upd_max(f[i][j][l][r], f[i + 1][j][l][r] + change(a[i] == l));
                    upd_max(f[i][j][l][r], f[i][j - 1][l][r] + change(a[j] == r));
                    upd_max(f[i][j][l][r], f[i + 1][j - 1][l][r] + change(a[i] == r) + change(a[j] == l));
                }
            }
        }
    }
    printf("%d\n", f[1][n][1][tot]);
}