CF311B Cats Transport

传送门

思路：

开始想没什么思路，想到的是贪心，就是能一起走的肯定要尽量一起走

所以我就将猫玩耍的时间 \(t_i\) 减去路程的长度 \(\sum_{k=2}^i d_k\) ，令结果为 \(a\)，这样当他们的 \(a\) 值相同时，就表示可以一起走

然后我们会发现，对于某一些猫，如果他们要一起走，那么等待的时间就是 \(\sum Max - a_i\) ，这里 \(Max\) 为这群猫 \(a_i\) 的最大值

这样我们就将问题转化成将 \(a_i\) 排序，然后将他们分成 \(p\) 段，设每段范围为 \([l_k,r_k]\)，求 \(\sum_{k=1}^p \sum_{i=l_k}^{r_k} Max_k - a[i]\) 的最小值

状态转移方程为：

\[dp[i][k]=dp[j][k-1]+(i-j)\times a_i-(sum_i-sum_j) \]

其中 \(sum_i=\sum_{k=1}^i a_k\)

这样我们就可以用斜率优化 \(O(np)\) 解决

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
inline int reads()
{
    int sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
int n, m, p;
int q[100005][105], l[105], r[105];
int d[100005];
LL dp[100005][105], a[100005], sum[100005];
inline bool check(int ty, int j, double k_i)
{
    double k_j = 1.0 * (dp[q[j][ty]][ty] + sum[q[j][ty]] - dp[q[j - 1][ty]][ty] - sum[q[j - 1][ty]]) / (q[j][ty] - q[j - 1][ty]);
    return k_i >= k_j;
}
inline bool cmp(int ty, int num)
{
    double k_i = 1.0 * (dp[num][ty] + sum[num] - dp[q[r[ty]][ty]][ty] - sum[q[r[ty]][ty]]) / (num - q[r[ty]][ty]);
    double k_j = 1.0 * (dp[q[r[ty]][ty]][ty] + sum[q[r[ty]][ty]] - dp[q[r[ty] - 1][ty]][ty] - sum[q[r[ty] - 1][ty]]) / (q[r[ty]][ty] - q[r[ty] - 1][ty]);
    return k_i <= k_j;
}
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
#endif
    n = reads(), m = reads(), p = reads();
    for(int i = 2; i <= n; i++) d[i] = d[i - 1] + reads();
    for(int i = 1; i <= m; i++)
    {
        int h = reads(), t = reads();
        a[i] = t - d[h];
    }
    std::sort(a + 1, a + 1 + m);
    for(int i = 1; i <= m; i++)
        sum[i] = sum[i - 1] + a[i];
    q[l[0] = r[0] = 1][0] = 0;
    for(int i = 1; i <= m; i++)
    {
        for(int k = 0; k <= std::min(i - 1, p); k++)
        {
            for(int j = l[k]; j <= r[k]; j++)
            {
                bool L = j == l[k] ? true : check(k, j, a[i]), R = j == r[k] ? false : check(k, j + 1, a[i]);
                if(L && !R)
                {
                    dp[i][k + 1] = dp[q[j][k]][k] + sum[q[j][k]] - q[j][k] * a[i] + a[i] * i - sum[i];
                    l[k] = j;
                    break;
                }
            }
            while(r[k + 1] > l[k + 1] && cmp(k + 1, i)) r[k + 1]--;
            q[++r[k + 1]][k + 1] = i;
        }
    }
    printf("%lld", dp[m][p]);
    return 0;
}
cf题解斜率优化

相关

LG5308 [COCI2019] Quiz（wqs二分+斜率优化DP）

斜率优化

斜率优化

算法学习笔记之斜率优化

[bzoj] 1597 土地购买 || 斜率优化dp

BZOJ1767 [CEOI2009] Harbingers - 树上斜率优化

标签