P4072 [SDOI2016]征途

额...很难想象这题我调了好长时间....

首先我们不难得出答案就是

min{m*\sum{x^2}-(\sum{x})^2}

最小化中间那个平方

做法一是斜率优化

细节有:

斜率不要带负数单调递减......
注意double的用法
直接使用滚动数组即可,除了求值完全基于上个数组

做法二再加上wqs二分凑齐凸优化

细节:判断的时候别用你妈的eps

f[n].se>=m的时候就统计答案

还用longlong

斜率优化
code:


#include<bits/stdc++.h>
#define db double
#define ll long long
using namespace std;
const int MAXN = 3e3 + 7;
int n, m;
int a[MAXN], sum[MAXN];
int que[MAXN];
ll f[MAXN], g[MAXN];

inline ll calc(int x, int y) {
	return g[y] + 1ll * (sum[x] - sum[y]) * (sum[x] - sum[y]);
}

inline db k(int x) {
	return 2.0 * sum[x];
}

//y f_x+sum_x^2
inline ll gety(int b) {
	return g[b] + 1ll * sum[b] * sum[b];
}
//x sum_x
//k 2*sum_k
//b f_y-sum_y^2
inline db getslope(int x, int y) {
	return (gety(y) - gety(x)) / (sum[y] - sum[x]);//del(y)/del(x);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		sum[i] = sum[i - 1] + a[i];
		g[i] = sum[i] * sum[i];
		// printf("%d?\n", sum[i]);
	}
	int h = 1, t = 1;
	for(int j = 2; j <= m; ++j) {
		h = 1, t = 1;
		que[h] = j - 1;
		for(int i = 1; i <= n; ++i) {
			f[i] = 0;
		}
		for(int i = j; i <= n; ++i) {
			while(h < t && getslope(que[h], que[h + 1]) < k(i)) {
				// printf("%d %d %d %lf %lf\n", i, que[h], que[h + 1], getslope(que[h], que[h + 1]), k(i));
				++h;
			}
			// printf("%d %d %d %lf %lf\n", i, que[h], que[h + 1], getslope(que[h], que[h + 1]), k(i));
			// printf("in->%d %d?%d %d\n", i, que[h], h, t);
			f[i] = calc(i, que[h]);
			// printf("dedaole :%d?%d %d?\n", f[i], g[que[h]], sum[i] - sum[que[h]]);
			// if(h < t)
			// 	printf("now tb is :%lf?%lf\n", getslope(que[h], que[h + 1]), k(i));
			while(h < t && getslope(que[t], que[t - 1]) > getslope(que[t], i))
				--t;
			que[++t] = i;
		}
		for(int i = 1; i <= n; ++i) {
			g[i] = f[i];
		}
	}
	printf("%lld\n", 1ll * m * f[n] - 1ll * sum[n] * sum[n]);
	return 0;
}


#include<bits/stdc++.h>
#define db double
#define ll long long
#define fi first
#define se second
#define pii pair<ll,int>
#define mkp(x,y) (make_pair(x,y))
using namespace std;
const int MAXN = 3e3 + 7;
const db eps = 1e-7;
int n, m;
int a[MAXN];
ll sum[MAXN];
int que[MAXN];
pii f[MAXN];

inline pii calc(int x, int y) {
	return mkp(f[y].fi + 1ll * (sum[x] - sum[y]) * (sum[x] - sum[y]), 1 + f[y].se);
}

inline db k(int x) {
	return 2.0 * sum[x];
}

//y f_x+sum_x^2
inline ll gety(int b) {
	return f[b].fi + 1ll * sum[b] * sum[b];
}
//x sum_x
//k 2*sum_k
//b f_y-sum_y^2
inline db getslope(int x, int y) {
	return (db)(gety(y) - gety(x)) / (db)(sum[y] - sum[x]);//del(y)/del(x);
}

inline pii solve(int x) {
	int h = 1, t = 1;
	for(int i = 1; i <= n; ++i) {
		f[i].fi = 0;
		f[i].se = 0;
	}
	que[h] = 0;
	for(int i = 1; i <= n; ++i) {
		while(h < t && getslope(que[h], que[h + 1])  < k(i)) {
			// printf("%d %d %d %lf %lf\n", i, que[h], que[h + 1], getslope(que[h], que[h + 1]), k(i));
			++h;
		}
		// printf("%d %d %d %lf %lf\n", i, que[h], que[h + 1], getslope(que[h], que[h + 1]), k(i));
		// printf("in->%d %d?%d %d\n", i, que[h], h, t);
		f[i] = calc(i, que[h]);
		f[i].fi += x;
		// printf("dedaole :%d?%d %d?\n", f[i], f[que[h]], sum[i] - sum[que[h]]);
		// if(h < t)
		// 	printf("now tb is :%lf?%lf\n", getslope(que[h], que[h + 1]), k(i));
		while(h < t && getslope(que[t], que[t - 1])  > getslope(que[t], i))
			--t;
		que[++t] = i;
	}
	return f[n];
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		sum[i] = sum[i - 1] + a[i];
		// g[i] = sum[i] * sum[i];
		// printf("%d?\n", sum[i]);
	}
	int l = -1e9, r = 1e9, mid, Ans = 0;
	for(int i = 1; i <= 36; ++i) {
		mid = (l + r) >> 1;
		// printf("%d %d %d\n", l, r, mid);
		solve(mid);
		if(f[n].se > m) {
			l = mid;
		} else {
			Ans = f[n].fi - m * mid;
			r = mid;
		}
	}
	printf("%lld\n", 1ll * m * Ans - 1ll * sum[n]*sum[n]);
	return 0;
}

夏晓光(loveJY)的博客

P1973 [NOI2011]NOI 嘉年华