网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P9688
2023-11-04
【LGR-161-Div.3】洛谷基础赛 #4 P9688 Colo.
原题链接:P9688Colo.很显然,能够共存的颜色一定不会相交,所以可以记录每个颜色最左边的位置和最右边的位置,我们对于每个颜色只考虑,这个颜色左边的可以和这个颜色共存的额颜色用f[i][j]表示当前考虑i这种颜色,选i这种颜色,然后在i这种颜色之前(包括这种颜色)一共选了j种颜色的最大价值
2023-10-04
『题解』P9688
题目传送门思路:设有两个颜色\(x_1x_2\),两端分别为\(l_1\)\(r_1\),\(l_2\)\(r_2\)。通过观察可以发现,若满足\(x_1<x_2\)且\(r_1>l_2\)则\(x_1x_2\)一定是单调不下降的。那么我们可以先预处理出一个颜色可以与前面的哪些颜色构成单调不下降,然后用dp求出最终答案
2023-10-02
P9688
\(Solution\)考虑dp。观察数据范围,\(n,k\leq500\)的数据几乎明示了同阶下\(\Theta(n^3)\)的算法了。那么直接往这里考虑。设\(f_{i,j}\)为当前是第\(i\)中颜色,且已经选了\(j\)种颜色的最大值。那么有以下转移方程:\[f_{i,k}=\max^{i-1}_{j=1}cmp(i,j)\landf_{j,k