You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
typedef long long LL;
|
|
|
|
|
|
const int N = 100010;
|
|
|
|
|
|
const int P = 110;
|
|
|
|
|
|
int n, m;
|
|
|
|
|
|
int p;
|
|
|
|
|
|
int q[N];
|
|
|
|
|
|
|
|
|
|
|
|
LL d[N], t[N];
|
|
|
|
|
|
LL a[N], s[N];
|
|
|
|
|
|
LL f[P][N];
|
|
|
|
|
|
int h;
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
cin >> n >> m >> p;
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 2; i <= n; i++) cin >> d[i], d[i] += d[i - 1]; // 从2开始
|
|
|
|
|
|
for (int i = 1; i <= m; i++) cin >> h >> t[i], a[i] = t[i] - d[h], s[i] = s[i - 1] + a[i];
|
|
|
|
|
|
sort(a + 1, a + m + 1); // 由小到大排序,m只小猫
|
|
|
|
|
|
|
|
|
|
|
|
// dp初始
|
|
|
|
|
|
memset(f, 0x3f, sizeof f);
|
|
|
|
|
|
for (int i = 0; i <= p; i++) f[i][0] = 0; // 出动i个饲养员，接0只小猫，等待0。将DP TABLE第一列修改为0
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= p; i++) { // 饲养员
|
|
|
|
|
|
int hh = 0, tt = 0; // 哨兵
|
|
|
|
|
|
for (int j = 1; j <= m; j++) { // 遍历小猫
|
|
|
|
|
|
// 凸包的斜率单调上升，并且，直线的斜率也是单调上升
|
|
|
|
|
|
// 准备在下凸壳中找到第一个斜率大于k的直线，小于k的全部剔除
|
|
|
|
|
|
while (hh < tt && (f[i - 1][q[hh + 1]] + s[q[hh + 1]] - f[i - 1][q[hh]] - s[q[hh]]) <= a[j] * (q[hh + 1] - q[hh]))
|
|
|
|
|
|
hh++;
|
|
|
|
|
|
// 推出的公式
|
|
|
|
|
|
f[i][j] = f[i - 1][q[hh]] + a[j] * (j - q[hh]) - (s[j] - s[q[hh]]);
|
|
|
|
|
|
// 维护下凸壳 [下面是 k=(y1-y2)/(x1-x)的PK，大的干掉。同时，为了避免除法，采用了十字相乘法变形]
|
|
|
|
|
|
while (hh < tt && (f[i - 1][j] + s[j] - f[i - 1][q[tt]] - s[q[tt]]) * (q[tt] - q[tt - 1]) <= (f[i - 1][q[tt]] + s[q[tt]] - f[i - 1][q[tt - 1]] - s[q[tt - 1]]) * (j - q[tt]))
|
|
|
|
|
|
tt--;
|
|
|
|
|
|
// 加入
|
|
|
|
|
|
q[++tt] = j;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
cout << f[p][m] << endl;
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
