Palindrome Bo

有圣贤名曰 Sam ，曾云“ Really difficult. ”。

题目链接： HDU 2016 多校 。

题目描述：

定义一个子序列合法当且仅当：

• 子序列为回文子序列。
• 子序列为单谷子序列。

给定长度 $n\le 5000$ 的序列 $a(1\le a_i\le n)$ ，求其最长合法子序列长度以及本质不同的最长合法子序列个数。

我们先看第一问。可以发现，一个合法的子序列，结构必然是一个类似于“洋葱”的结构，即 ABCDEFGFEDCBA 这样的结构。

所以我们不妨考虑定义 $f_{i,j}$ 表示当这个“洋葱”最外层为 $i$ 和 $j$ （其中 $a_i=a_j$ ）时的最大合法子序列长度。那么此时就有一个的显然的转移：枚举 $i<x \le y<j$ 且 $a_x=a_y$ ，则 $f_{i,j}=\max\{f_{x,y}+2\}$ ，边界情况 $f_{i,i}=1$ 。

这个算法的复杂度为 $\mathcal{O}(n^4)$ 。

接下来考虑优化。不妨固定左端点 $i$ ，从左往右枚举 $j$ ，并维护一个值 $ans$ 表示区间 $(i,j]$ 里的最大 $f$ 值。那么当枚举到一个 $j$ 时，我们有如下两个行动：

1. 若 $a_i=a_j$ ，则 $f_{i,j}=ans+2$ 。
2. 若 $a_i\ge a_j$ ，则我们枚举一个 $i<k\le j$ ，进行 $f_{k,j}\to ans$ 。

这样就完成了转移。

上述复杂度为 $\mathcal{O}(n^3)$ 。

观察一个性质：若 $i<x\le y<j$ ，则必然有 $f_{i,j}>f_{x,y}$ 。即，区间包含关系中较大的区间必然更优。

由此我们可以对上面的 DP 进行优化。设 $nxt_{i,j}$ 表示 $\min\{k\mid a_k=j,i<k\}$ ， $pre_{i,j}=\max\{k\mid a_k=j,k<i\}$ 。即 $i$ 前后第一个 $j$ 的位置。那么固定 $i$ ，枚举 $j$ 后，若 $a_i\ge a_j$ ，则不需要枚举 $k$ ，可以直接 $f_{nxt_{i,a_j},j}\to ans$ 。

这样就可以做到 $\mathcal{O}(n^2)$ ，第一问就做完了。

接下来考虑在第一问的基础上做第二问。

定义 $g_{i,j}$ 表示最长的本质不同的子序列个数。

首先，如果没有“本质不同”的限制，则可以直接做一个简单的计数 DP 。

那么接下来，还是固定 $i$ ，枚举 $j$ ，对于 $a_i\ge a_j$ ，令 $cnt$ 表示合法子序列长度为 $ans$ 时的本质不同子序列的个数。令 $k=nxt_{i,a_j}$ ，则：

• 若 $ans<f_{k,j}$ ，更新 $ans=f_{k,j},cnt=g_{k,j}$ 。
• 否则，若 $ans=f_{k,j}$ ，此时我们执行 $cnt+g_{k,j}\to cnt$ 。但是这样我们可能会计算重复的。那么，自然的，所有与这个方案重复的方案必然也是满足 $a_k=a_j=a_x$ 的区间 $[k,x]$ ，这个 $x$ ，由于上面的性质，可以得到 $x=pre_{i,a_j}$ 。那么只需要再让 $cnt-g_{k,x}\to cnt$ 即可。

于是这道题我们就做完了。复杂度 $\mathcal{O}(n^2)$ 。