题目

为了加快社会主义现代化，建设新农村，农夫约(Farmer Jo)决定给农庄做一些防火措施，保障自己、猫、奶牛的生命安全。

农夫约的农庄里有N+1 座建筑，排成了一排，编号为0～N。对于0 <=i < N，建筑i 有w[i]头奶牛居住，与建筑i+1 距离为d[i]。建筑N 已装有消防栓，现在，农夫约决定再给k 个建筑安装消防栓，以减小安全隐患。

当火灾来临时，所有奶牛会从所在建筑开始，向大编号方向逃生，直到遇上第一个消防栓（如果本来就在消防栓处，就不用跑了）。农夫约定义了一个隐患值val：所有奶牛逃生距离之和。

农夫约希望让隐患值尽可能小，需要你给他设计一个好方案。

分析

设 \(f_{i,l}\) 表示做到第 \(i\) 个，已经装了 \(l\) 个安全栓时最小答案

转移时枚举一个 \(j\)，为了能快速转移，我们需要一些辅助数组

设 \(g_i\) 表示 \(i\) 之前的所有奶牛到 \(i\) 的总逃生距离

\(s_i，d_i\) 分别表示题中 \(w，d\) 的前缀和

那么 \(f_{i,j} = \min f_{j,l-1}+g_i-g_j-(d_{i-1} - d_{j-1})\times s_j\)

对于 \(j=0\) 是为了不越界特殊处理

由于它是 \(O(n^2k)\) 的，我们还需斜率优化

\(Code\)

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long LL;

const int N = 1e6 + 5 , K = 25;

int n , k , pre[N][K] , q[N];

LL f[N][3] , d[N] , dd[N] , s[N] , g[N];

void print(int p , int k)

{

	if (p) print(pre[p][k] , k - 1);

	else return;

	printf("%d " , p - 1);

}

inline double slope(int x , int y , int l)

{

	LL X1 , X2;

	if (x == 0) X1 = f[x][l & 1 ^ 1];

	else X1 = f[x][l & 1 ^ 1] - g[x] + s[x] * d[x - 1];

	if (y == 0) X2 = f[y][l & 1 ^ 1];

	else X2 = f[y][l & 1 ^ 1] - g[y] + s[y] * d[y - 1];

	return 1.0 * (X1 - X2) / (s[x] - s[y]);

}

inline LL read()

{

	LL res = 0;

	char ch = getchar();

	while (ch < '0' || ch > '9') ch = getchar();

	while (ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + ch - '0' , ch = getchar();

	return res;

}

int main()

{

	freopen("life.in" , "r" , stdin);

	freopen("life.out" , "w" , stdout);

	n = read() , k = read();

	for(register int i = 1; i <= n; i++) s[i] = read() , d[i] = dd[i] = read();

	for(register int i = 1; i <= n + 1; i++)

		s[i] += s[i - 1] , d[i] += d[i - 1] , g[i] = g[i - 1] + s[i - 1] * dd[i - 1];

	for(register int i = 0; i <= n + 1; i++)

		for(register int j = 0; j <= 1; j++) f[i][j] = 1e17;

	f[0][0] = 0;

	int h , t;

	for(register int l = 1; l <= k + 1; l++)

	{

		q[h = t = 1] = 0;

		for(register int i = 1; i <= n + 1; i++)

		{

			while (h < t && slope(q[h] , q[h + 1] , l) < d[i - 1]) h++;

			if (q[h] == 0) f[i][l & 1] = f[q[h]][l & 1 ^ 1] + g[i];

			else f[i][l & 1] = f[q[h]][l & 1 ^ 1] + g[i] - g[q[h]] - (d[i - 1] - d[q[h] - 1]) * s[q[h]];

			pre[i][l] = q[h];

			while (h <= t && slope(q[t - 1] , q[t] , l) > slope(q[t] , i , l)) t--;

			q[++t] = i;

		}

	}

	printf("%lld\n" , f[n + 1][(k + 1) & 1]);

	print(pre[n + 1][k + 1] , k);

}

巴特西

JZOJ 5355. 【NOIP2017提高A组模拟9.9】保命

题目

分析

\(Code\)

最新文章

热门文章