CF1799D2 Hot Start Up (hard version) 题解

why_cb · 2023-02-28 18:34:42 · 题解

祭， CF 第一次 A 看不懂摆烂去做 D 结果 D2 混杂 D1 代码交赛后十秒发现数组没开大。

（我还是太逊了）

首先先看 D1 ，

我们发现两个 CPU 显然是等价的，所以确定了一个 CPU 运行的程序，那么另一个便确定了。

由此，对于暴力的 n^3 DP，我们考虑简化状态。

对于当前 f_{i,j} 表示第 i 次程序在一个 CPU 上运行完，另一个 CPU 上一次运行的程序是 j，

这样就可以分两种情况 n^2 从 f_i 转移到 f_{i+1}：

• ```cpp f[i+1][j]=min(f[i+1][j],f[i][j]+(a[i]==a[i+1]?h[a[i+1]]:c[a[i+1]])) ```
• ```cpp f[i+1][a[i]]=min(f[i+1][a[i]],f[i][j]+(j==a[i+1]?h[a[i+1]]:c[a[i+1]])); ```

最后在 f_n 中取最小值即可。

再看 D2 ，显然是要求优化 DP 是复杂度降低到 O(n\log n)。

观察之前的二维 DP ， f_{i-1} 与 f_i （此时反过来好思考一点）之间的转移也分为两种情况（与之前的两个情况相对应）：

• 对于所有的 f_{i,j} 等于 f_{i-1,j} 加上 c_{a[i]} 或者 h_{a[i]}（由 a_i 是否等于 a_{i-1} 决定）。

• 对于 f_{i,a[i-1]} 还可以取 \min{f_{i-1}}+c_{a[i]} 与 f_{i-1,a[i]}+h_{a[i]} 中间的最小值

（由之前的转移方程直接抽象而来，可以画图理解）。

区间查询最小值，区间加，单点修改的线段树便可以实现。

Code：

build(1,0,k);
for(int i=1;i<=n;i++)
{
    ll res=min(query(1,0,k)+c[a[i]],query(1,a[i],a[i])+h[a[i]]);//区间查询
    update(1,0,k,a[i]==a[i-1]?h[a[i]]:c[a[i]]);//区间加
    if(res<query(1,a[i-1],a[i-1])) update(1,a[i-1],res);//单点修改
}
printf("%lld\n",query(1,0,k));