Codeforces 311B Cats Transport【斜率优化DP】

LINK

---

题目大意

有一些猫，放在一些位置，人一步移动一个位置

给出每个猫出现的时间，每个人可以自由安排其出发时间，沿途已经出现的猫捡起，猫等待的时间是被减去的时间减去出现的时间

猫可以等人，人不能等猫

现在有P个人，问猫等待的总时间T最小是多少。

思路

首先可以算出要捡起每个猫最早出发的时间是多少\(c_i\)

然后按照这个值排序，每个人捡起的猫一定是在这个值上连续的一段

然后计算出如果一个人选\([l,r]\)，等待时间到达每个猫的时间减去到个猫最小的时间，是\(c_r*(r-l+1)-(s_r-s_{l-1})\)

其中s是c的前缀和，为什么呢？因为c是刚好捡起没个猫的时间，所以\(c_r-c_i\)就是刚好捡起r时候i的等待时间

然后就变成了\(dp_{i,j}=dp_{k,j-1}+c_i*(i-k)-(s_i-s_k)\)

转化一下发现\(x'=k,k'=c_i,y'=dp_{k,j-1}+s_k,b'=dp_{i,j}+s_i-i*c_i\)

斜率单调递增，最小化截距，直接维护下凸壳就可以了

---

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

//typename

typedef long long ll;

typedef pair<int, int> pi;

//convenient for

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

//inf of different typename

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

//fast read and write

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

//c_i = t_i - d_i

//s_i = \sum_{j=1}^i c_j

//dp[i][j] = min(dp[k][j - 1] + c_i * (i - k) - (s_i - s_k)

const int N = 1e5 + 10;

const int K = 1e2 + 10;

ll n, m, p;

ll d[N], s[N], c[N];

ll dp[N][K];

struct Node {ll x, y;} q[N];

ll operator * (const Node a, const Node b) {

  return a.x * b.y - a.y * b.x;

}

Node operator - (const Node a, const Node b) {

  return (Node){a.x - b.x, a.y - b.y};

}

ll calc(Node a, ll pos) {

  return a.y - s[pos] + c[pos] * (pos - a.x);

}

int main() {

  freopen("input.txt", "r", stdin);

  Read(n), Read(m), Read(p);

  fu(i, 2, n) Read(d[i]), d[i] += d[i - 1];

  fu(i, 1, m) {

    int t, h; Read(h), Read(t);

    c[i] = t - d[h];

  }

  sort(c + 1, c + m + 1);

  fu(i, 1, m) {

    s[i] = s[i - 1] + c[i];

    dp[i][1] = - s[i] + i * c[i];

  }

  int l, r;

  fu(j, 2, p) {

    q[l = r = 1] = (Node) {0ll, 0ll};

    fu(i, 1, m) {

      while (l < r && calc(q[l], i) >= calc(q[l + 1], i)) ++l;

      dp[i][j] = calc(q[l], i);

      Node now = (Node){i, dp[i][j - 1] + s[i]};

      while (l < r && (q[r] - now) * (q[r - 1] - now) > 0) --r;

      q[++r] = now;

    }

  }

  Write(dp[m][p]);

  return 0;

}