LOJ#2353货币兑换

CDQ分治优化斜率优化DP。

有个结论就是每天买完卖完....知道这个之后考虑今天卖的是哪天买的就能写出n²DP了。

发现形式是f_i = max(a_ib_j + c_id_j)的形式。我们可以把c_i除出来，就是斜率优化了。

然后发现横坐标和斜率全部没有单调性，于是CDQ分治搞一搞。

1 #include
2
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 11 return;
12 }
13
14 inline bool cmp_k(const int &a, const int &b) {
15 return k[a] 16 }
17
18 inline bool cmp_w(const int &a, const int &b) {
19 return w[a] 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] = " <39 //printf("f = %.3f \n", f[r]);
40 return;
41 }
42 int mid = (l + r) >> 1;
43 CDQ(l, mid);
44
45 /// update
46 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 convex
50 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 f
61 //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 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] = " <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 }
AC代码

eps很重要...