CF813D Two Melodies 题解

选两个非空、互不相交的子序列，各自满足"相邻音符相差 \(1\) 或模 \(7\) 同余"，求长度和的最大值。\(n \le 5000\)，\(a_i \le 10^5\)。

1. 朴素 DP：\(f[i][x][y]\)

扫描到第 \(i\) 个音符，两条旋律末尾值为 \(x,y\)（\(0\) 表示该旋律为空）时的最大总长度。扫到 \(v=a_{i+1}\)：

跳过：\(f[i+1][x][y] \gets \max(f[i+1][x][y],\ f[i][x][y])\)
接第一条（\(x=0\) 或 \(x\sim v\)）：\(f[i+1][v][y] \gets f[i][x][y]+1\)
接第二条（\(y=0\) 或 \(y\sim v\)）：\(f[i+1][x][v] \gets f[i][x][y]+1\)

状态数 \(n\cdot10^{10}\)，开不出来。

2. 消掉 \(i\)：\(g[x][y]\)

三个转移的合法性判断都不含 \(i\)，它只表示"扫到哪"；而任意状态都能靠"跳过"传到最后一层，所以整维滚掉。

剩下 \(10^{10}\) 个状态，仍太大。

3. 关键观察

最后一层里，任何非初始状态都满足两个末尾至少有一个等于 \(v=a_n\) —— 一个下标不能同时进两条旋律。于是只需维护"以 \(v\) 为端点"的转移：

\[g'[v][y] = \max\Big(g[v][y],\ 1+\max_{x=0 \text{ 或 } x\sim v} g[x][y]\Big) \]

4. 陷阱：直接开全局桶是错的

设 \(\text{best}[t] = \max\{g[x][y] \mid x=t \text{ 或 } y=t\}\)，转移看似只需 \(1+\max(\text{best}[v\pm1],\ \text{bestMod}[v\bmod7])\)，\(O(1)\) 完事。但这是错的。

结论：桶只压缩了"用来判定相容的那一维"，配对信息必须留着 → 钉住一个端点。

5. 钉住端点：\(dp[i][j]\)

\[dp[i][j] = \text{两条旋律末尾分别在位置 } i,j\ (i

\(dp\) 对 \(i,j\) 对称，"哪条是第一"无意义。令 \(a[0]=0\) 为虚拟位置，则 \(dp[0][j]\) = 以 \(j\) 结尾的最长单旋律长度。

位置维度在这里足够：\(i 保证两条旋律不交叉，转移来源 \(k 保证接在末尾之后。

设第二条旋律倒数第二个元素在 \(k\)（\(k，\(k\ne i\)，\(a[k]\sim a[j]\)）：

\[dp[i][j] = 1 + \max\Big(\{\,dp[0][i]\,\} \cup \{\,dp[k][i] \mid k

朴素 \(O(n^3)\)，超时。

6. 开桶 + 前缀优化 \(\Rightarrow O(n^2)\)

固定 \(i\)，\(j\) 从 \(i+1\) 递增。转移对 \(k\) 的枚举只用 \(a[k]\) 的值，位置范围限制已由枚举顺序保证，故可开两桶：

\(\text{best}[v]\)：另一个端点值为 \(v\) 的最优
\(\text{bestMod}[r]\)：另一个端点值 \(\equiv r \pmod 7\) 的最优

一轮 \(i\) 的生命周期：

开局：把 \(k\in[0,i)\) 的 \(dp[k][i]\) 按 \(a[k]\)、\(a[k]\bmod 7\) 入桶（覆盖第二项）
扫描中：每算出 \(dp[i][j']\)（\(i）立刻入桶（这就是前缀优化，第三项自动被覆盖）
收尾：清桶

\[dp[i][j] = 1 + \max\Big(dp[0][i],\ \text{best}[a[j]-1],\ \text{best}[a[j]+1],\ \text{bestMod}[a[j]\bmod 7]\Big) \]

答案：\(\max\{dp[i][j] \mid 1\le i。\(i\ge1\) 保证第一条非空，\(n\ge2\) 保证答案 \(\ge2\).

AC code

#include 
using namespace std;
using ll = long long;

const int N = 5005;
const int MAXA = 100005;

int n, a[N], dp[N][N];
int val[MAXA], mod[7];

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0);

    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    int ans = 0;
    for (int i = 0; i < n; i ++) {
        for (int k = 0; k < 7; k ++) mod[k] = 0;
        // 开局：k < i 的 dp[k][i] 入桶
        for (int k = 0; k < i; k ++) {
            val[a[k]] = max (val[a[k]], dp[k][i]);
            mod[a[k] % 7] = max (mod[a[k] % 7], dp[k][i]);
        }
        for (int j = i + 1; j <= n; j++) {
            int res = dp[0][i] + 1;
            res = max (res, val[a[j] - 1] + 1);
            res = max (res, val[a[j] + 1] + 1);
            res = max (res, mod[a[j] % 7] + 1);
            dp[i][j] = res;
            // 先算再入桶，否则 a[j] 被自己用两次；这一步即前缀优化
            val[a[j]] = max (val[a[j]], dp[i][j]);
            mod[a[j] % 7] = max (mod[a[j] % 7], dp[i][j]);
            if (i > 0) ans = max (ans, dp[i][j]);
        }
        for (int k = 0; k <= n; k++) val[a[k]] = 0;
    }

    cout << ans << "\n";
    return 0;
}

复杂度

时间 \(O(n^2)\)，空间 \(O(n^2+A)\)