Description
小 Y 最近在一家金券交易所工作. 该金券交易所只发行交易两种金券:\(A\) 纪念券 (以下简称 \(A\) 券) 和 \(B\) 纪念券 (以下简称 \(B\) 券). 每个持有金券的顾客都有一个自己的帐户. 金券的数目可以是一个实数. 每天随着市场的起伏波动, 两种金券都有自己当时的价值, 即每一单位金券当天可以兑换的人民币数目. 我们记录第 \(k\) 天中 \(A\) 券和 \(B\) 券的价值 分别为 \(A_k\) 和 \(B_k\) (元/单位金券). 为了方便顾客, 金券交易所提供了一种 非常方便的交易方式: 比例交易法. 比例交易法分为两个方面:
- 卖出金券: 顾客提供一个 \([0, 100]\) 内的实数 \(op\) 作为卖出比例, 其意义为: 将 \(op%\) 的 \(A\) 券和 \(op%\) 的 \(B\) 券以当时的价值兑换为人民币;
- 买入金券: 顾客支付 \(ip\) 元人民币, 交易所将会兑换给用户总价值为 \(ip\) 的金券, 并且, 满足提供给顾客的 \(A\) 券和 \(B\) 券的比例在第 \(k\) 天恰好为 \(rate_k\);
例如, 假定接下来 3 天内的 Ak、Bk、RateK 的变化分别为:
| 时间 | \(A_k\) | \(B_k\) | \(rate_k\) |
|---|---|---|---|
| 第一天 | \(1\) | \(1\) | \(1\) |
| 第二天 | \(1\) | \(2\) | \(2\) |
| 第三天 | \(2\) | \(2\) | \(3\) |
假定在第一天时, 用户手中有 \(100\) 元人民币但是没有任何金券. 用户可以执行以下的操作:
| 时间 | 用户操作 | 人民币 (元) | \(A\) 券的数量 | \(B\) 券的数量 |
|---|---|---|---|---|
| 开户 | 无 | \(100\) | \(0\) | \(0\) |
| 第一天 | 买入 \(100\) 元 | \(0\) | \(50\) | \(50\) |
| 第一天 | 卖出 \(50\%\) | \(75\) | \(25\) | \(25\) |
| 第二天 | 买入 \(60\) 元 | \(15\) | \(55\) | \(40\) |
| 第三天 | 卖出 \(100\%\) | \(205\) | \(0\) | \(0\) |
注意到, 同一天内可以进行多次操作. 小 Y 是一个很有经济头脑的员工, 通过较长时间的运作和行情测算, 他已经知道了未来 \(n\) 天内的 \(A\) 券和 \(B\) 券的价值以及 \(rate\). 他还 希望能够计算出来, 如果开始时拥有 \(S\) 元钱, 那么 \(n\) 天后最多能够获得多少元钱.
Input
输入第一行两个正整数 \(n, S\), 分别表示小 Y 能预知的天数以及初始时拥有的钱数.
接下来 \(n\) 行, 第 \(k\) 行三个实数 \(A_k, B_k, rate_k\), 意义如题目中所述.
Output
只有一个实数 \(MaxProfit\), 表示第 \(n\) 天的操作结束时能够获得的最大的金钱数目. 答案保留 \(3\) 位小数.
Sample Input
3 100
1 1 1
1 2 2
2 2 3Sample Output
225.000Data Range
对于 60% 的测试数据, 满足:\(n \leq 1000\);
对于 100% 的测试数据, 满足:\(n \leq 100000\);
对于 100% 的测试数据, 满足:\(0 \lt A_k, B_k \leq 10, 0 \lt rate_k \leq 100, MaxProfit \leq 10^9\)
Explanation
题目似乎 \(O(n^2)\) 比较好水, 但是 \(O(n \log n)\) 就不太好想......
然后黄学长写了一个 CDQ 分治做 DP?!
就发现其实就是斜率优化加归并动规 (雾)~
原文链接:http://hzwer.com/3508.html
此题见 cdq 论文
首先 \(n^2\) 的 dp 很好做
额然后是 cdq 分治
理论不是很难但是没写过还是比较蛋疼
理论就看 cdq 论文即可...... 然后代码......
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maximize(__x,__y) __x=max(__x,__y)
using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 100100;
const llf infinit = 1e20;
const llf epsilon = 1e-9;
struct point {
llf a, b, rate;
llf x, y, k;
int id; };
bool operator < (point a, point b) {
return a.k > b.k; }
int n, stk[maxn];
llf dp[maxn];
point p[maxn], tmp[maxn];
llf slope(int a, int b)
{
if (!b) return -infinit;
if (fabs(p[a].x - p[b].x) < epsilon)
return infinit;
return (p[b].y - p[a].y) / (p[b].x - p[a].x);
}
void solve(int l, int r)
{
if (l == r) {
dp[l] = max(dp[l], dp[l-1]);
p[l].y = dp[l] / (p[l].a * p[l].rate + p[l].b);
p[l].x = p[l].rate * p[l].y;
return ;
} // Close to the final, shall recurse hitherto
int mid = (l + r) / 2;
for (int i = l, l1 = l, l2 = mid+1; i <= r; i++) {
if (p[i].id <= mid)
tmp[l1++] = p[i];
else
tmp[l2++] = p[i];
} // Splitting into two parts, left and right
for (int i = l; i <= r; i++)
p[i] = tmp[i]; // And copy them back from buffer
// Conquer the left part
solve(l, mid);
// A conves hull for the left and the right, respectively
int stop = 0;
for (int i = l; i <= mid; i++) {
while (stop > 1 && slope(stk[stop-1], stk[stop]) - slope(stk[stop-1], i) < epsilon)
stop -= 1;
stk[++stop] = i;
} // A convex hull for the left
stk[++stop] = 0;
for (int i = mid+1, j = 1; i <= r; i++) {
while (j < stop && p[i].k - slope(stk[j], stk[j+1]) < epsilon)
j += 1;
maximize(dp[p[i].id], p[stk[j]].x*p[i].a + p[stk[j]].y*p[i].b);
} // A convex hull for the right
// Conquer the right part
solve(mid+1, r);
// Combining the two parts
for (int i = l, l1 = l, l2 = mid+1; i <= r; i++) {
if ( l1 <= mid && ( p[l1].x < p[l2].x
|| (fabs(p[l1].x - p[l2].x) < epsilon && p[l1].y < p[l2].y)
|| l2 > r ))
tmp[i] = p[l1++];
else
tmp[i] = p[l2++];
}
for (int i = l; i <= r; i++)
p[i] = tmp[i];
return ;
}
int main(int argc, char** argv)
{
scanf("%d%lf", &n, &dp[0]);
for (int i = 1; i <= n; i++) {
scanf("%lf%lf%lf", &p[i].a, &p[i].b, &p[i].rate);
p[i].k = -p[i].a / p[i].b;
p[i].id = i;
}
sort(p + 1, p + n + 1);
// CDQ Divide and Conquer
solve(1, n);
printf("%.3lf\n", dp[n]);
return 0;
}