题解归档 - cf813D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf813D
• 本地来源：problems/cf813D/idea.md
• 题目链接：https://codeforces.com/contest/813/problem/D
• 原始标题：cf813D — Two Melodies

思路

cf813D — Two Melodies

题意

给定长度 $n$ 的音符序列，选两个非空、不交的子序列，各自相邻元素满足 $|a_i-a_j|=1$ 或 $a_i \equiv a_j \pmod 7$（旋律条件），最大化两子序列长度之和。

思路

定义 $dp[x][y]$：一条旋律最后一个元素在位置 $x$，另一条在位置 $y$（$0$ 表示该条为空）时的最大长度和。

• 若 $x=y$，答案为 $0$（同一位置不能共用）。
• 若 $x<y$，由对称性 $dp[x][y]=dp[y][x]$。
• 若 $x>y$，只能从 $dp[i][y]$（$i<x,\, i\neq y$）转移：在第一条旋律末尾追加 $a_x$。

追加 $a_x$ 时，前驱 $a_i$ 与 $a_x$ melody 相邻当且仅当：

1. $a_i = a_x \pm 1$
2. $a_i \equiv a_x \pmod 7$

优化（$O(n^2)$）

固定第二维 $y$，按 $x$ 递增扫描。维护：

• maxmod[j]：已扫过的 $dp[i][y]$ 中，$a_i \bmod 7 = j$ 的最大值
• maxnum[v]：已扫过的 $dp[i][y]$ 中，$a_i = v$ 的最大值

则

$$dp[x][y] = \max\bigl(\maxnum[a_x\pm1]+1,\; \maxmod[a_x\bmod 7]+1,\; dp[0][y]+1\bigr)$$

外层 $y=0..n$，总复杂度 $O(n^2)$，$n\le 5000$ 可过。

实现要点

• 初始 $dp[0][0]=0$，其余为 $-\infty$。
• 最终答案：$\max_{x,y\ge 1} dp[x][y]$（两条均非空）。
• 样例 1：$[1,2]$ 与 $[4,5]$，和为 $4$。
• 样例 2：$[62,48,49]$ 与 $[60,61]$，和为 $5$。

验证

• 样例通过（Kali run_exe.py）。
• stress.py -n 50 与暴力对拍全部通过。

参考

• Educational Round 22 Editorial — 813D

代码

来源：problems/cf813D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:49:40
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=5005;
const ll maxa=100005;
const ll neg=-1e9;
ll s[maxn+5],dp[maxn+5][maxn+5],maxmod[7],maxnum[maxa+5];
ll n,i,j,x,y,ans,cur;
int main(){
    cin>>n;
    for(i=1;i<=n;i++) cin>>s[i];
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++) dp[i][j]=neg;
    dp[0][0]=0;
    for(y=0;y<=n;y++){
        for(j=0;j<7;j++) maxmod[j]=neg;
        for(i=1;i<=n;i++){
            maxnum[s[i]]=neg;
            if(s[i]>1) maxnum[s[i]-1]=neg;
            maxnum[s[i]+1]=neg;
        }
        dp[0][y]=dp[y][0];
        for(x=1;x<y;x++){
            dp[x][y]=dp[y][x];
            maxnum[s[x]]=max(maxnum[s[x]],dp[x][y]);
            maxmod[s[x]%7]=max(maxmod[s[x]%7],dp[x][y]);
        }
        for(x=y+1;x<=n;x++){
            cur=neg;
            if(s[x]>1) cur=max(cur,maxnum[s[x]-1]+1);
            cur=max(cur,maxnum[s[x]+1]+1);
            cur=max(cur,maxmod[s[x]%7]+1);
            cur=max(cur,dp[0][y]+1);
            dp[x][y]=cur;
            maxnum[s[x]]=max(maxnum[s[x]],dp[x][y]);
            maxmod[s[x]%7]=max(maxmod[s[x]%7],dp[x][y]);
        }
        for(x=1;x<=n;x++)
            if(y>0) ans=max(ans,dp[x][y]);
    }
    cout<<ans<<"\n";
    return 0;
}