题解：P16692 染色 Plus

· · 题解

题意简述

每种颜色只能用于一个给定区间，涂一格有固定费用。需要给每个位置选择一种可用颜色，并保证任意连续 K 格不全为同色。求最小总费用，无解时输出 -1。

解题思路

先证明每个位置只需保留费用最低的三种可用颜色。

取任意合法方案。若位置 i 使用的颜色不在费用最低的三种之中，就观察它当前左右相邻位置的颜色。左右至多出现两种颜色，所以最低的三种颜色中至少有一种与两侧都不同。

把位置 i 改成这种颜色后，它所在的同色连续段长度变为 1。因此，不会新产生长度达到 K 的同色段，费用也不会增加。每次替换都会减少使用非前三颜色的位置数。重复操作后，一定能得到只使用前三种颜色的最优方案。

接下来求出每个位置的三种最低费用颜色。把所有颜色按费用递增排序，再依次扫描它的可用区间。每个位置只需被访问三次；取得三种颜色后，后续颜色都不再有用。

用并查集维护每个位置右侧第一个尚未填满的位置。设 fa[i] 表示从 i 开始的下一个未满位置。某个位置收集到三种颜色时，令它的父亲指向下一个位置。于是，扫描区间时可以跳过所有已经填满的位置。排序需要 O(m\log m)，并查集部分只产生至多 3n 次有效访问。

下面进行动态规划。令 f_{i,c} 表示涂完前 i 格，且最后一段颜色为 c 时的最小费用。再定义：

g_{i,c}=\min_{d\ne c}f_{i,d}

设结尾的同色段从 t+1 开始。它的长度为 i-t，必须满足 i-t<K。若该段颜色为 c，代价为 (i-t)C_c，所以：

f_{i,c}=\min_t\left(g_{t,c}+(i-t)C_c\right)

其中决策范围为：

\max(0,i-K+1)\le t<i

把只与 t 有关的部分整理后得到：

f_{i,c}=iC_c+\min_t\left(g_{t,c}-tC_c\right)

对每种颜色分别维护一个单调队列。队列元素记录决策点 t 和数值 g_{t,c}-tC_c，并让数值单调递增。

查询位置 i 时，先删除所有 t<i-K+1 的元素。此时，队首就是合法决策的最小值。

只在颜色 c 属于位置 t+1 的前三种颜色时，加入决策点 t；只在它属于位置 i 的前三种颜色时，计算 f_{i,c}。颜色本身的可用范围是连续区间，所以两个端点均可用时，整个同色段都可使用颜色 c。

每个位置至多有三种保留颜色。生成 g_{i,c} 时，只需枚举上一位置的至多三个状态，并排除颜色 c。

为了避免覆盖仍要使用的上一层状态，代码先为当前位置的所有颜色加入决策点。随后，再统一计算当前位置的状态。

当 i=1 时，加入虚拟决策 t=0，其前缀费用为 0。最后在位置 n 的所有状态中取最小值。若所有状态均不可达，则输出 -1。

排序的时间复杂度为 O(m\log m)。并查集、动态规划和全部单调队列的总操作数均为 O(n+m)，空间复杂度为 O(n+m)。

正确性证明

最低费用的三种颜色足以保留，这一点已由逐点替换证明。替换后的颜色与左右两色都不同，所以不会扩大任何已有同色段；替换又不增加费用。因此，至少存在一个最优方案只使用每个位置保留的颜色。

再证明动态规划转移。任意以颜色 c 结尾的方案都有唯一的最后同色段 [t+1,i]。此前位置 t 的颜色必须不是 c，最优前缀费用就是 g_{t,c}。最后一段长度小于 K，费用为 (i-t)C_c。转移枚举了全部合法的 t，也没有加入非法方案。

最后证明单调队列。队列只保存当前长度限制内的决策点，并按 g_{t,c}-tC_c 递增。删除过期元素后，队首恰好是转移式中的最小值。每个决策点只会从队尾或队首删除一次，维护不会改变可选决策集合的最小值。

因此，算法完整覆盖一个最优的前三颜色方案，并准确求出每个状态，最终答案正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct Color
{
    int l,r,c;
}a[N];
struct Queue
{
    vector<pair<int,ll>> q;
    int head=0;
    void add(int x,ll y)
    {
        if(head==q.size())
        {
            q.clear();
            head=0;
        }
        while(q.size()>head&&q.back().second>=y)q.pop_back();
        q.push_back({x,y});
    }
    ll ask(int x,int k)
    {
        while(head<q.size()&&q[head].first<x-k+1)head++;
        return head==q.size()?inf:q[head].second;
    }
}que[N];
int fa[N];
ll f[N];
vector<int> use[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
bool cmp(Color x,Color y){return x.c<y.c;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)cin>>a[i].l>>a[i].r>>a[i].c;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=n+1;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        for(int j=find(a[i].l);j<=a[i].r;j=find(j+1))
        {
            use[j].push_back(i);
            if(use[j].size()==3)fa[j]=find(j+1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(auto x:use[i])
        {
            ll val=i==1?0:inf;
            if(i>1)for(auto y:use[i-1])if(x!=y)val=min(val,f[y]);
            if(val<inf)que[x].add(i-1,val-1LL*(i-1)*a[x].c);
        }
        for(auto x:use[i])f[x]=que[x].ask(i,k)+1LL*i*a[x].c;
    }
    ll ans=inf;
    for(auto x:use[n])ans=min(ans,f[x]);
    cout<<(ans>inf/2?-1:ans)<<'\n';
    return 0;
}