CH 5A01 (简化版)
Bzoj 2726 (斜率优化版)
题意：见上。
很容易想出二维DP，即$dp(i,j)$表示前$i$个任务分了$j$个的最小值。
本题没有限制分多少份，所以第二维我们想一想是不是不必要的？
删去第二维我们就不能之前前面执行了多少次$S$，那么就算不出来，所以这里有一种方法是将费用提前计算。
设$dp(i)$表示前$i$个任务最小值。
则
$$
dp(i)=\min(dp(j)+\sum_{k=1}^i T_k \times \sum_{k=j+1}^i C_k + S \times \sum_{k=j+1}^n C_k)
$$
注意到后面的$S \times \sum_{k=j+1}^n C_k)$，这个就是将费用提前计算了，因为选择了这样的方式必然会对后面的任务产生这样的贡献，所以可以提前计算。
然后式子显然能斜率优化。但是斜率不单增，在凸壳中二分即可。则Bzoj 2726可解。
知识点：
1、DP 费用提前计算
2、斜率优化实数会被卡精度，用叉积来判
3、二分
//CH 5A01
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 5000 + 5;
const LL INF = 2223372036854775808ll;
int n, s, T[MAXN], C[MAXN];
LL Tsum[MAXN], Csum[MAXN], dp[MAXN];
void clean() {
}
int solve() {
clean();
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; ++i) scanf("%d%d", &T[i], &C[i]);
Tsum[0] = Csum[0] = 0;
for (int i = 1; i <= n; ++i) Tsum[i] = Tsum[i - 1] + T[i], Csum[i] = Csum[i - 1] + C[i];
for (int i = 0; i <= n; ++i) dp[i] = INF;
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
LL tT = Tsum[i];
LL tC = Csum[i] - Csum[j], tC2 = Csum[n] - Csum[j];
dp[i] = min(dp[i], dp[j] + tT * tC + s * tC2);
}
}
cout << dp[n];
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
//Bzoj 2726
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#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 = 300000 + 5;
LL n, S, tt[MAXN], cc[MAXN];
LL T[MAXN], C[MAXN], dp[MAXN], que[MAXN], l, r;
//db getK(LL a, LL b) {return 1.0 * (dp[a] - dp[b]) / (C[a] - C[b]);}
LL fnd(db w) {
if (l == r) return l;
LL x = 1, y = r; // 只到 r
while (x < y) {
LL mid = (x + y) >> 1;
//if (getK(que[mid], que[mid + 1]) <= w) x = mid + 1; else y = mid; 实数会被卡精度
if (dp[que[mid + 1]] - dp[que[mid]] <= w * (C[que[mid + 1]] - C[que[mid]])) x = mid + 1; else y = mid;
}
return x;
}
void clean() {
ms(T, 0), ms(C, 0), ms(dp, 0);
}
int solve() {
clean();
scanf("%lld%lld", &n, &S);
for (LL i = 1; i <= n; ++i) scanf("%lld%lld", &tt[i], &cc[i]);
for (LL i = 1; i <= n; ++i) C[i] = C[i - 1] + cc[i], T[i] = T[i - 1] + tt[i];
l = r = 1, que[1] = 0;
for (LL i = 1; i <= n; ++i) {
LL pos = fnd(S + T[i]);
dp[i] = dp[que[pos]] - (S + T[i]) * C[que[pos]] + T[i] * C[i] + S * C[n];
//while (l < r && getK(que[r], que[r - 1]) >= getK(i, que[r])) --r;
while (l < r && (dp[que[r]] - dp[que[r - 1]]) * (C[i] - C[que[r]]) >= (dp[i] - dp[que[r]]) * (C[que[r]] - C[que[r - 1]])) --r;
que[++r] = i;
}
cout << dp[n];
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
