[NOI2007]货币兑换

嘟嘟嘟

懒的写博客了，恰好发现自己的思路跟某一老哥极其像，所以各位还是看这篇博客吧

写的CDQ分治，感觉不是很懂，以后还得再复习一遍。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define rg register typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 1e5 + 5; inline ll read() {ll ans = 0;char ch = getchar(), last = ' ';while(!isdigit(ch)) {last = ch; ch = getchar();}while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();}if(last == '-') ans = -ans;return ans; } inline void write(ll x) {if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x % 10 + '0'); }int n; db s, a[maxn], b[maxn], rat[maxn]; int q[maxn], qry[maxn];inline bool cmp(int i, int j) {return a[i] * b[j] < a[j] * b[i]; }db dp[maxn], ans = 0; struct Point {db x, y;inline bool operator < (const Point& oth)const{return x < oth.x || (x == oth.x && y < oth.y);} }p[maxn], que[maxn];inline bool slope(Point k, Point j, Point i) {return (j.x - i.x) * (k.y - i.y) - (j.y - i.y) * (k.x - i.x) <= 0; } inline db calc(Point j, int i) {return j.x * a[i] + j.y * b[i]; }inline void cdqSolve(int L, int R) {if(L == R){if(dp[L - 1] > dp[L]) dp[L] = dp[L - 1];p[L].y = dp[L] / (rat[L] * a[L] + b[L]);p[L].x = rat[L] * p[L].y;return;}int mid = (L + R) >> 1, id1 = L, id2 = mid + 1, l = 1, r = 0;for(int i = L; i <= R; ++i) q[qry[i] <= mid ? id1++ : id2++] = qry[i];for(int i = L; i <= R; ++i) qry[i] = q[i];cdqSolve(L, mid);for(int i = L; i <= mid; ++i){while(r > 1 && slope(que[r - 1], que[r], p[i])) --r;que[++r] = p[i];}for(int i = mid + 1; i <= R; ++i){int j = qry[i];while(l < r && calc(que[l], j) <= calc(que[l + 1], j)) ++l;dp[j] = max(dp[j], calc(que[l], j));}cdqSolve(mid + 1, R);if(L == 1 && R == n) return;l = id1 = L; id2 = mid + 1;while(l <= R){if(id2 > R || (id1 <= mid && p[id1] < p[id2])) que[l++] = p[id1++];else que[l++] = p[id2++];}for(int i = L; i <= R; ++i) p[i] = que[i];return; }int main() {n = read(); scanf("%lf", &s);for(int i = 1; i <= n; ++i) scanf("%lf%lf%lf", &a[i], &b[i], &rat[i]), qry[i] = i;sort(qry + 1, qry + n + 1, cmp);dp[0] = s;cdqSolve(1, n);printf("%.3lf\n", dp[n]);return 0; }

转载于:https://www.cnblogs.com/mrclr/p/10132644.html

总结

以上是生活随笔为你收集整理的[NOI2007]货币兑换的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。