题解：P10381 「HOI R1」杂赛选比

xiaoliebao1115 · 2024-04-28 18:17:04 · 题解

官方线段树太难打了，所以我用堆来优化。

动态规划

定义 dp_i 为算到当前位置，并选择向后设置解锁的最大答案。

更新 dp_i 时，比如从 dp_j 更新，要求 dp_j 设置解锁时一定能覆盖到 dp_i，则之间的每个数都可以选择增加贡献，所以就有 dp_i=dp_j+ \begin{aligned}\sum_{k=j+1}^{i-1}\end{aligned}a_k，求和可以用前缀和求解。

所以在所有 j+a_j\ge i 的 dp_j 当中选出一个 dp_j+\begin{aligned}\sum_{k=j+1}^{i-1}\end{aligned}a_k 最大的数更新 dp_i。

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

优化

以 dp_j+\begin{aligned}\sum_{k=j+1}^{n}\end{aligned}a_k 为第一关键字，j+a_j 为第二关键字压入优先队列。

在更新时，每次取出头 x，判断这个是否能覆盖当前 dp_i，若不能，弹出，若能，dp_i 应该等于 x 的第一关键字减去 \begin{aligned}\sum_{k=i}^{n}\end{aligned}a_k，即是减去多余部分，并跳出循环。

时间复杂度 O(n\log n)。

code

这里给出关键部分。

for(int i=2;i<=n;i++)
{
    while(1)
    {
        if(q.top().second>=i||q.empty()) break;
        q.pop();
    }
    if(q.empty()) continue;
    /*
    for(int j=1;j<i;j++)
    {       
        if(a[j]+j>=i)
        {
            dp[i]=max(dp[i],dp[j]+sum[i-1]-sum[j]);
        }
    }*/
    dp[i]=q.top().first-(sum[n]-sum[i-1]);
    q.push({dp[i]+sum[n]-sum[i],i+a[i]});
}

最后的答案就是所有数中最大的 dp_i+a_i，即是把这个数换成不向后设置而选择增加答案。