首页 > ACM题库 > HDU-杭电 > HDU 3842-Machine Works-分治-[解题报告]HOJ
2015
04-13

HDU 3842-Machine Works-分治-[解题报告]HOJ

Machine Works

问题描述 :

You are the director of Arbitrarily Complex Machines (ACM for short), a company producing advanced machinery using even more advanced machinery. The old production machinery has broken down, so you need to buy new production machines for the company. Your goal is to make as much money as possible during the restructuring period. During this period you will be able to buy and sell machines and operate them for profit while ACM owns them. Due to space restrictions, ACM can own at most one machine at a time.

During the restructuring period, there will be several machines for sale. Being an expert in the advanced machines market, you already know the price Pi and the availability day Di for each machines Mi. Note that if you do not buy machine Mi on day Di, then somebody else will buy it and it will not be available later. Needless to say, you cannot buy a machine if ACM has less money than the price of the machine.

If you buy a machine Mi on day Di, then ACM can operate it starting on day Di + 1. Each day that the machine operates, it produces a profit of Gi dollars for the company.

You may decide to sell a machine to reclaim a part of its purchase price any day after you’ve bought it. Each machine has a resale price Ri for which it may be resold to the market. You cannot operate a machine on the day that you sell it, but you may sell a machine and use the proceeds to buy a new machine on the same day.

Once the restructuring period ends, ACM will sell any machine that it still owns. Your task is to maximize the amount of money that ACM makes during the restructuring.

输入:

The input consists of several test cases. Each test case starts with a line containing three positive integers N, C, and D. N is the number of machines for sale (N <= 10^5), C is the number of dollars with which the company begins the restructuring (C <= 10^9), and D is the number of days that the restructuring lasts (D <= 10^9).

Each of the next N lines describes a single machine for sale. Each line contains four integers Di, Pi, Ri and Gi,
denoting (respectively) the day on which the machine is for sale, the dollar price for which it may be bought, the
dollar price for which it may be resold and the daily profit generated by operating the machine. These numbers satisfy
1 <= Di <= D, 1 <= Ri < Pi <=10^9 and 1 <= Gi <= 10^9.

The last test case is followed by a line containing three zeros.

输出:

The input consists of several test cases. Each test case starts with a line containing three positive integers N, C, and D. N is the number of machines for sale (N <= 10^5), C is the number of dollars with which the company begins the restructuring (C <= 10^9), and D is the number of days that the restructuring lasts (D <= 10^9).

Each of the next N lines describes a single machine for sale. Each line contains four integers Di, Pi, Ri and Gi,
denoting (respectively) the day on which the machine is for sale, the dollar price for which it may be bought, the
dollar price for which it may be resold and the daily profit generated by operating the machine. These numbers satisfy
1 <= Di <= D, 1 <= Ri < Pi <=10^9 and 1 <= Gi <= 10^9.

The last test case is followed by a line containing three zeros.

样例输入:

6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1
0 0 0

样例输出:

Case 1: 44

本题是利用cdq分治  实现斜率优化的一个题目

斜率优化之前做的几个题都是斜率单调,并且插入点时由于点在某一维单调,所以仅仅操作队首和队尾就能完成优化了

但是本题显然不是 

主要参考了两个东西

从《Cash》谈一类分治算法的应用

(Day1)cdq分治相关

这两个直接在百度上搜 ,第一个出来的就是

本题的题意是

一个公司获得了一个厂房n(10^5)天的使用权
和一笔启动资金C(10^9),准备在n天里租借机器生产来获得收益
可以租借的机器有M(10^5)个,每个机器有四个值,D,P,R,G (D<=n, P,R,G都是10^9)
表明你可以再第D天花费P费用(首先手里必须有那么多钱)
租借这个机器,从D+1天开始该机器每天产生G的收益,在你不需要机器时
可以卖掉这个机器,一次获得R的钱

需要注意的是:
厂房里只能停留一台机器
不能再购买和卖出机器的那天操作机器,但是可以再同一天卖掉一台机器再买一台
在第n+1天,必须卖掉手里的机器
问n+1天后能获得的最大资金

根据这个题意

我们可以得到一个dp转移方程

首先要想的问题是是否有场地就要放机器

最开始的时候肯定不是这样,因为怕买到坑的机器很可能会亏钱,但是假设你买到了一台好的机器,在下一个机器进来之前,你肯定是一直运转下去的

然后得把所有的时间都离散化,就是每个机器的D

然后用f[i]表示在D[i]时刻卖掉手里的机器手里最多多少钱

f[i] = max(f[i - 1], f[j] – P[j] + R[j] + G[j] * (D[i] – D[j]  - 1))

其中f[j] >= P[j]

可以看出是O(n^2)的,显然不行啊

令h[j] = f[j] + R[j]- P[j] – G[j] * (D[j] + 1)

式子就变成  f[i] = h[j] + D[i] * G[j]

即h[j] = -D[i] * G[j] + f[i] 

对于这个, 可以抽象成一个二维空间

由(G[j],h[j])作为点集, -D[i]为斜率

然后求使得截距最大的那个,就是f[i]最大了

观察这些点集

可以发现,一点都不单调啊,就需要按照G[j]这一维做个排序

使得他至少在一维上单调,方便我们做插入和删除操作

然后由于斜率是单调递减的,并且是负数

可以画一画,最后要维护的最优点的点集,在图上形成的是一条上凸的线

Machine Works

然后每插一个点都是维护这个图形

然后这个排序,你在普通的DP方法里肯定是不能每次都去排序的

这就需要cdq分治了

对于一个区间l,r

你先更新了l,mid

然后对左边这部分的区间的点集, 进行排序,形成上面这个图形

然后更新右边区间的时候,

由于斜率是递减的,你可以发现,我们只需要扫一遍这个图形即可完成所有右边区间值的更新

然后就这样递归着去更新

完成cdq分治

总体复杂度,应该是nlognlogn

因为每个子区间中都有这个排序

代码还是参照xiaodao的,因为实在是不熟悉这个方法。

需要留意的是,在斜率之间做比较的时候,如果用乘法来比较的话,会溢出long long

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <set>
#include <vector>
#include <map>
#define MAXN 11111
#define MAXM 55555
#define INF 1000000007
using namespace std;
long long f[111111];
struct node {
    int d, p, g, r;
}p[111111];
bool cmp(node x, node y) {
    return x.d < y.d;
}
int n, d;
typedef pair<int, long long> PA;
PA A[111111], C[111111];
long long h(int j) {
    return f[j] + (long long)p[j].r - (long long)p[j].p - (long long)p[j].g * (long long)(p[j].d + 1);
}
int slopecomp(PA a, PA b, PA c) {
    long long xa = b.first - a.first;
    long long xb = c.first - a.first;
    long long ya = b.second - a.second;
    long long yb = c.second - a.second;
    double tmp = (double)xa * yb - (double)xb * ya;
    return tmp < 0;
}
void cdq(int l, int r) {
    if(l + 1 <= r) {
        int m = (l + r) >> 1;
        cdq(l, m);
        int na = 0, nb = 0, nc = 0;
        for(int j = l; j <= m; j++) {
            if(f[j] >= p[j].p) A[na++] = PA(p[j].g, h(j));
        }
        sort(A, A + na);
        for(int i = 0; i < na; i++) {
            while(nc > 1 && !slopecomp(C[nc - 1], C[nc], A[i])) nc--;
            C[++nc] = A[i];
        }
        int j = 0;
        for(int i = m + 1; i <= r; i++) {
            long long a1, a2, b1, b2, x;
            x = p[i].d;
            while(j < nc) {
                a1 = C[j].first;
                a2 = C[j + 1].first;
                b1 = C[j].second;
                b2 = C[j + 1].second;
                if(a1 * x + b1 >= a2 * x + b2) break;
                j++;
            }
            f[i] = max(f[i], (long long)C[j].first * x + C[j].second);
        }

        cdq(m + 1, r);
    }
}
int main() {
    int cas = 0;
    while(scanf("%d%I64d%d", &n, &f[0], &d) != EOF) {
        if(n == 0 && f[0] == 0 && d == 0) break;
        for(int i = 1; i <= n; i++) scanf("%d%d%d%d", &p[i].d, &p[i].p, &p[i].r, &p[i].g);
        sort(p + 1, p + n + 1, cmp);
        ++n;
        p[n].d = d + 1;
        p[n].g = p[n].p = 0;
        for(int i = 1; i <= n; i++) f[i] = f[0];
        cdq(0, n);
        printf("Case %d: %I64d\n", ++cas, f[n]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sdj222555/article/details/40919903


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }