CDQ分治优化斜率优化DP。
有个结论就是每天买完卖完....知道这个之后考虑今天卖的是哪天买的就能写出n²DP了。
发现形式是fi = max(aibj + cidj)的形式。我们可以把ci除出来，就是斜率优化了。
然后发现横坐标和斜率全部没有单调性，于是CDQ分治搞一搞。
1 #include2 3 const int N = 1000010; 4 const long double eps = 1e-12; 5 6 long double a[N], b[N], c[N], R[N], f[N], s, k[N], v[N], w[N]; 7 int n, node[N], t[N], stk[N], top; 8 9 template inline void Max(T &a, const T &b) {10 a < b ? a = b : 0;11 return;12 }13 14 inline bool cmp_k(const int &a, const int &b) {15 return k[a] < k[b];16 }17 18 inline bool cmp_w(const int &a, const int &b) {19 return w[a] < w[b];20 }21 22 inline bool check(int a, int b, int c) {23 if((v[b] - v[a]) * (w[c] - w[b]) + eps >= (v[c] - v[b]) * (w[b] - w[a])) {24 return 1;25 }26 return 0;27 }28 29 void CDQ(int l, int r) {30 31 //printf("CDQ : l = %d r = %d \n", l, r);32 33 if(l == r) {34 if(r > 1) f[r] *= b[r];35 Max(f[r], f[r - 1]);36 v[r] = -f[r] / c[r];37 w[r] = -v[r] * R[r];38 //std::cout << "v[i] = " << v[r] << std::endl;39 //printf("f = %.3f \n", f[r]);40 return;41 }42 int mid = (l + r) >> 1;43 CDQ(l, mid);44 45 /// update46 memcpy(t + l, node + l, (r - l + 1) * sizeof(int));47 std::sort(t + l, t + mid + 1, cmp_w);48 std::sort(t + mid + 1, t + r + 1, cmp_k);49 // build convex50 stk[top = 1] = t[l];51 if(mid - l + 1 >= 2){52 stk[++top] = t[l + 1];53 for(int i = l + 2; i <= mid; i++) {54 while(top > 1 && check(stk[top - 1], stk[top], t[i])) {55 top--;56 }57 stk[++top] = t[i];58 }59 }60 // update f61 //printf("top = %d \n", top);62 int head = 1;63 for(int i = mid + 1; i <= r; i++) {64 int x = t[i];65 while(head < top && (v[stk[head]] - v[stk[head + 1]]) / (w[stk[head]] - w[stk[head + 1]]) + eps < k[x]) {66 head++;67 }68 int y = stk[head];69 //printf("Max %.3f %.3f * %.3f \n", f[x], -v[y], (R[y] * a[x] + b[x]));70 //Max(f[x], -v[y] * (R[y] * a[x] + b[x]));71 Max(f[x], w[y] * k[x] - v[y]);72 }73 74 CDQ(mid + 1, r);75 return;76 }77 78 int main() {79 80 //freopen("in.in", "r", stdin);81 //freopen("my.out", "w", stdout);82 83 scanf("%d%Lf", &n, &s);84 for(int i = 1; i <= n; i++) {85 scanf("%Lf%Lf%Lf", &a[i], &b[i], &R[i]);86 c[i] = a[i] * R[i] + b[i];87 //std::cout << "c[i] = " << c[i] << std::endl;88 k[i] = a[i] / b[i];89 node[i] = i;90 }91 92 f[1] = s;93 94 CDQ(1, n);95 96 printf("%.3Lf\n", f[n]);97 return 0;98 }
eps很重要...