2015
04-13

# 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

(Day1)cdq分治相关

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

#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;
}

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));
}
}