题解 CF813D 【Two Melodies】

2019-01-09 22:10:40


题意

定义一段弦乐是好听的,当且仅当相邻元素相差 $1$ 或者 $7$ 的倍数。给你一段乐谱,求两段不相交的好听的弦乐的长度和的最大值。

分析

设 $f[i][j]$ 表示第一段到了 $i$ ,第二段到了 $j$ 的最大长度。容易写出 $O(n^3)$ 的DP。

考虑怎么优化。设 $maxmod[k]$ 表示最大的满足 $a[j]\equiv k\pmod 7$ 的最大的 $f[i][j]$ , $maxnum[k]$ 表示最大的满足 $a[j]=k$ 的 $f[i][j]$ 。

然后状态转移方程优化为: $f[i][j]=\max\left\{f[i][0],maxmod[a[j]\%7],maxnum[a[j]-1],maxnum[a[j]+1]\right\}+1$ 。

每次计算出一个dp值都要更新 $maxmod$ 和 $maxnum$ 。

还有,可以只计算 $j>i$ 的dp值,计算完后再将 $f[i][j]$ 赋值给 $f[j][i]$ 。

时间复杂度是 $O(n^2)$ 的。

代码

M_sea's blog