Codeforces 311B (二维斜率优化DP)

发表于 | 分类于 | | + s

Codeforces 311B
题意：有$m$只猫，放在一些位置$[1,n]$，每个位置之间的距离$d_i$，每个猫出现的时间$t_i$，假设派出$P$个人，可以自由安排其出发时间，沿途将已经出现的猫取掉，猫等待的时间是被取的时间减去出现的时间。现在有$P$个人，问总时间$T$最小是多少。

考虑设$a_i= t_i - \sum_\limits{j=1}^{h_i} d_i$，那么这个时间即为人什么时候出发，能取到猫$i$。
那么如果人出发时间为$g$，则该猫的等待时间为$a_i - g$(能取到的话)。
那么这样题目清楚了很多，如果$P=1$，那么答案就是最大值减去其他所有值的和。

考虑$p \leq 2$的情况：
我们可以发现这些猫现在的$a_i$和位置没有关系了，可以考虑将$a_i$按从小到大排序，然后发现只用用$P$个序列覆盖$a_i$即可。
这样还是麻烦，注意观察，序列一定是子串。因为不连续的一定不优，假设有$[1,3],[4,5],[6,8]$，则如果$[1,3], [6,8]$一个人，那么一定没有$[4, 5], [6,8]$一个人优。

所以可以开始DP：设$dp(i,j)$为分了$i$段，前$j$只猫的最小等待值，则
$$
dp(i,j)=\min_{1 \leq k \leq j} (dp(i-1,k)+a_j \cdot (j-k) - (\operatorname{sum}(j) - \operatorname{sum}(k)))
$$
直接枚举会炸。发现这里有$j,k$的乘积项，考虑斜率优化。
转化，得
$$
dp(i-1,k)+\operatorname{sum}(k)=dp(i,j)-a_j \cdot j + a_j \cdot k +\operatorname{sum}(j)
$$
那么决策可以写作点$(k, dp(i-1,k)+\operatorname{sum}(k))$
用这个算下斜率，即可斜率优化，注意开数组简化$dp(i-1,k)+\operatorname{sum}(k)$
并且一定要斜率大减小，避免负数对叉积的影响

知识点
1、斜率大减小，避免负数对叉积的影响
2、适当开数组简化一些东西

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 100000 + 5;

    LL n, m, p, d[MAXN], h[MAXN], t[MAXN];
    LL a[MAXN], sum[MAXN], dp[105][MAXN];
    LL q[MAXN], g[MAXN];

    void clean() {
        ms(dp, 0), ms(sum, 0);
    }
    int solve() {

        clean();
        scanf("%lld%lld%lld", &n, &m, &p);
        for (LL i = 2; i <= n; ++i) scanf("%lld", &d[i]), d[i] += d[i - 1];
        for (LL i = 1; i <= m; ++i) scanf("%lld%lld", &h[i], &t[i]);
        for (LL i = 1; i <= m; ++i) a[i] = t[i] - d[h[i]];

        sort(a + 1, a + 1 + m);
        for (LL i = 1; i <= m; ++i) sum[i] = sum[i - 1] + a[i];

        ms(dp, 0x3f);
        dp[0][0] = 0;

        for (LL i = 1; i <= p; ++i) {
            for (LL j = 1; j <= m; ++j) g[j] = dp[i - 1][j] + sum[j]; // 简化 
            LL l = 1, r = 1;
            q[1] = 0;
            for (LL j = 1; j <= m; ++j) {
                while (l < r && (g[q[l + 1]] - g[q[l]]) <= a[j] * (q[l + 1] - q[l])) ++l; // 斜率大减小，避免负数对叉积的影响 
                dp[i][j] = min(dp[i - 1][j], g[q[l]] + a[j] * (j - q[l]) - sum[j]);
                if (g[j] >= 0x3f3f3f3f3f3f3f3fll) continue ; // dp[i - 1][j] 为非法状态 
                while (l < r && (g[q[r]] - g[q[r - 1]]) * (j - q[r]) >= (g[j] - g[q[r]]) * (q[r] - q[r - 1])) --r; // 斜率大减小，避免负数对叉积的影响 
                q[++r] = j;
            }
        }

        printf("%lld\n", dp[p][m]);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------