每日一水第34弹(world final 2011 F)

一开始有一定的钱,给你n个交易日期,表示某一天某台机器的价格,你只能在这一天买这台机器,买了这台机器之后会从改天开始产生持续的收益,你可以在这之后的任意一天将这台机器再卖出去,你同时只能拥有一台机器。问最大的收益是多大。

dp[i]: the max money I can profit if I sell the machine int the Di_th day
just enum the day which I buy this machine to update the dp[i].
so we got this:
dp[i] = Max{dp[j] + (day[i]-day[j]-1)*profit[j]+sell[j]-buy[j]};
dp[i] = Max{profit[j] * day[i]+dp[j]+sell[j]-buy[j]-day[j]*profit[j]-profit[j]}
(for i = 0 -> j - 1)
so it's look like this
b = k * x + y;
y = -k * x + b;
k = day[i] , x = profit[j], y = dp[j]+sell[j]-buy[j]-day[j]*profit[j]-profit[j];
every previous state is an (x, y) Point. we just want a best (x, y) to update dp[i].
所以这是一条右上凸折线

左边的时间小于右边 左边按照x排序 右边按照斜率排序
由于归并排序可以顺便解决x排序 斜率排序可以在一开始解决好 每次到一个区间再根据
时间重新线性划分 这题比较特殊 斜率就是时间
有个坑就是x坐标可能会相等,这个时候要将y大的排在前面。
复杂度 nlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 200010;
const double eps = 1e-10;
long long f[N];
long long day[N], buy[N], sell[N], profit[N];
struct Point
{
    long long x, y;
    long long day;
    int id;
    int flag;
    Point()
    {
    }
    Point(long long x, long long day, int id)
    {
        flag=1;
        this->x = 1LL * x;
        this->day = day;
        this->id = id;
    }
};
int cmp(const Point &a, const Point &b)
{
    return a.day < b.day;
}
typedef long double ld;
struct Geometry
{
    Point p[N], tmp[N];
    long long dp[N];
    int stk[N];
    long double cross(Point o, Point a, Point b)
    {
        return (ld)(a.x - o.x) * (b.y - o.y) - (ld)(a.y-o.y)*(b.x-o.x);
    }
    long long getCost(int jj)
    {
        int j = p[jj].id;
        return 1LL * sell[j]-buy[j]-1LL*day[j]*profit[j]-profit[j];
    }
    inline void update(int j, int i)
    {
        if(p[j].flag==-1) return ;
        dp[i] = max(dp[i], 1LL * p[i].day * p[j].x + p[j].y);
    }
    void dfs(int l, int r)
    {
        if(l == r) {
           update(l - 1, l);
           if(dp[l] >= buy[p[l].id])
               p[l].y = dp[l] + getCost(l);
           else
               p[l].flag = -1, p[l].y = -1LL << 62;
           return ;
        }
        int mid = (l + r) >> 1;
        dfs(l, mid);
        int top = 0;
        for(int i = l; i <= mid; i++) {
            if(p[i].flag == -1) {
                continue;
            }
            while(top >= 2 && cross(p[i], p[stk[top - 1]], p[stk[top - 2]]) <= 0) {
                top--;
            }
            stk[top++] = i;
        }
        int pt = 0;
        if(top > 0)for(int i = mid + 1; i <= r; i++) {
            while(pt + 1 < top) {
                long long t1 = 1LL * p[i].day * p[stk[pt]].x + p[stk[pt]].y;
                long long t2 = 1LL * p[i].day * p[stk[pt+1]].x + p[stk[pt+1]].y;
                if(t2 < t1) {
                    break;
                }
                pt++;
            }
            dp[i] = max(dp[i], 1LL * p[i].day * p[stk[pt]].x + p[stk[pt]].y);
        }
        dfs(mid + 1, r);
        int p1 = l, p2 = mid + 1;
        for(int i = l; i <= r; i++) {
            if(p1 > mid) {
                tmp[i] = p[p2];
                p2++;
            } else if(p2 > r) {
                tmp[i] = p[p1];
                p1++;
            } else {
                if(p[p1].x < p[p2].x ¦¦ p[p1].x == p[p2].x && p[p1].y > p[p2].y ) tmp[i] = p[p1], p1++;
                else tmp[i] = p[p2], p2++;
            }
        }
        for(int i = l; i <= r; i++) {
            p[i] = tmp[i];
        }
    }
    void solve(int n)
    {
        sort(p + 1, p + n + 1, cmp);
        dfs(1, n);
 printf("%lld\n", dp[n]);
    }
}Ta;
Point p[N];
long long dp[N];
int main()
{
    int ca = 1, n, beginMoney, totalDays;
    while(scanf("%d%d%d", &n, &beginMoney, &totalDays) == 3) {
        if(n == 0 && beginMoney == 0 && totalDays == 0) break;
        for(int i = 1; i <= n; i++) {
            scanf("%lld%lld%lld%lld", &day[i], &buy[i], &sell[i], &profit[i]);
            p[i] = Ta.p[i] = Point(profit[i], day[i], i);
        }
        day[n + 1] = totalDays + 1;
        p[n+1] = Ta.p[n + 1] = Point(0, totalDays + 1, n + 1);
        p[0] = Ta.p[0] = Point(0, 0, 0);
        Ta.p[0].y = beginMoney;
        for(int i = 0; i <= n + 1; i++) Ta.dp[i] = beginMoney;
        printf("Case %d: ", ca++);
        Ta.solve(n + 1);
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注