题目

解析

很容易想到的 \(dp\)：

设 \(f_i\) 表示已经处理完 \(1..i\) 并且 \(i\) 是直接复制的需要的最小花费

那么 \(f_i=f_j+(i-j) \times (i-j-1)+c_i\)

这就是经典的斜率优化 \(dp\)，一般我们考虑两个决策谁会更优

考虑 \(j,k\) 两个决策，那么我们可以列个不等式，把它化成只关于 \(j\) 的式子和只关于 \(k\) 的式子放一边，剩下的放一边

再写成斜率的形式，具体分析怎么维护

式子如下：

\[\frac{2f_j+j^2+j-2f_k-k^2-k}{2j-2k} < i
\]

小于号维护下凸壳，斜率和横坐标都单调增，可以用单调队列维护

\(Code\)

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long LL;

const int N = 1e6 + 5;

const LL INF = 1e15;

int n;

LL f[N] , c[N] , q[N];

inline double slope(int x , int y)

{

	return (2.0 * f[y] + 1.0 * y * y + y - (2.0 * f[x] + 1.0 * x * x + x)) / (2.0 * y - 2.0 * x);

}

int main()

{

	scanf("%d" , &n);

	for(register int i = 1; i <= n; i++) scanf("%lld" , c + i);

	int h = 1 , t = 1;

	q[h] = 0;

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

	{

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

		f[i] = f[q[h]] + (LL)(i - q[h]) * (i - q[h] - 1) / 2 + c[i];

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

		q[++t] = i;

	}

	printf("%lld\n" , f[n]);

}

巴特西

JZOJ 3432. 【GDOI2014模拟】服务器

题目

解析

\(Code\)

最新文章

热门文章