bzoj1010: [HNOI2008]玩具装箱toy

窝只是来留坑的qwq

为毛别人家的乘积式可以过？

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<iostream>
 6 
 7 using namespace std;
 8 
 9 void setIO(const string& s) {
10     freopen((s + ".in").c_str(), "r", stdin);
11     freopen((s + ".out").c_str(), "w", stdout);
12 }
13 template<typename Q> Q read(Q& x) {
14     static char c, f;
15     for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1;
16     for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';
17     if(f) x = -x;
18     return x;
19 }
20 template<typename Q> Q read() {
21     static Q x; read(x); return x;
22 }
23 
24 typedef long long LL;
25 const int N = 50000 + 10;
26 
27 LL f[N], k[N], c;
28 
29 LL sqr(const LL& x) {
30     return x * x;
31 }
32 
33 LL up(int i) {
34     return k[i] * (k[i] + c * 2) + f[i];
35 }
36 
37 LL up(int i, int j) {
38     return up(j) - up(i);
39 }
40 
41 LL down(int i, int j) {
42     return 2 * (k[j] - k[i]);
43 }
44 
45 double slope(int i, int j) {
46     return up(i, j) / down(i, j);
47 }
48 
49 int q[N];
50 
51 int main() {
52 #ifdef DEBUG
53     freopen("in.txt", "r", stdin);
54     freopen("out.txt", "w", stdout);
55 #endif
56     
57     int n;
58     read(n), read(c), ++c;
59     for(int i = 1; i <= n; i++) k[i] = k[i-1] + read<int>();
60     for(int i = 1; i <= n; i++) k[i] += i;
61     
62     int L = 0, R = 0;
63     q[R++] = 0;
64     for(int i = 1; i <= n; i++) {
65         while(L + 1 < R && k[i] > slope(q[L], q[L + 1])) L++;
66 //        while(L + 1 < R && k[i] * down(q[L], q[L + 1]) > up(q[L], q[L + 1])) L++;
67         int j = q[L];
68         f[i] = f[j] + sqr(k[i] - k[j] - c);
69         while(L + 1 < R && slope(q[R - 2], q[R - 1]) > slope(q[R - 2], i)) R--;
70 //        while(L + 1 < R && up(q[R - 2], q[R - 1]) * down(q[R - 2], i) > up(q[R - 2], i) * down(q[R - 2], q[R - 1])) R--;
71         q[R++] = i;
72     }
73     
74     printf("%lld
", f[n]);
75     
76     return 0;
77 }

updated2016.3.23

把向量判断的又写了一遍

就过了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>

using namespace std;
template<typename Q> Q &read(Q &x) {
	static char c, f;
	for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1;
	for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	if(f) x = -x; return x;
}
template<typename Q> Q read() {
	static Q x; read(x); return x;
}

typedef long long LL;
const int N = 50000 + 10;

struct Point {
	LL x, y;
	Point() {}
	Point(LL x, LL y) : x(x), y(y) {}
	Point operator - (const Point &rhs) const {
		return Point(x - rhs.x, y - rhs.y);
	}
	LL f(LL k) const {
		return x * k + y;
	}
};

LL Cross(const Point &a, const Point &b) {
	return a.x * b.y - a.y * b.x;
}

Point p[N];
LL k[N], f[N];

LL sqr(const LL &x) {
	return x * x;
}

int main() {
#ifdef DEBUG
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	
	int n, c;
	read(n), ++read(c);
	for(int i = 1; i <= n; i++) {
		read(k[i]) += k[i-1] + 1;
	}
	
	int L = 0, R = 0;
	p[R++] = Point(0, 0);
	
	for(int i = 1; i <= n; i++) {
		while(L + 1 < R && p[L].f(k[i]) > p[L + 1].f(k[i])) L++;
		f[i] = p[L].f(k[i]) + sqr(k[i] - c);
		Point np(-2 * k[i], f[i] + k[i] * (k[i] + 2 * c));
		while(L + 1 < R && Cross(np - p[R - 2], np - p[R - 1]) >= 0) R--;
		p[R++] = np;
	}
	
	printf("%lld
", f[n]);
	
	return 0;
}