\(\text{solution}\)

比较显然的 \(dp\)

顺序既然无所谓，那为了方便处理贡献，就先排个序

然后设 \(f_i\) 表示分到前 \(i\) 个的最小工资

则 \(f_i=C+f_j+{(t_i-t_{j+1})}^2=C+f_j+{t_i}^2+{t_{j+1}}^2-2 \times t_i \times t_{j+1}\)

斜率优化下

若有 \(k<j\)，\(j\) 比 \(k\) 优

那么 \(((f_j+{t_{j+1}}^2)-(f_k+{t_{k+1}}^2))/(t_{j+1}-t_{k+1})<2\times t_i\)

单调队列维护下凸壳即可

#include<cstdio>

#include<algorithm>

#define LL long long

using namespace std;

const int N = 1e6 + 5;

const LL INF = 1e18;

LL f[N], t[N];

int n, k, C, Q[N];

inline void read(LL &x)

{

	x = 0; char ch = getchar();

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

	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();

} 

inline double slope(int j, int k)

{

	return 1.0 * (f[j] + t[j + 1] * t[j + 1] - f[k] - t[k + 1] * t[k + 1]) / (t[j + 1] - t[k + 1]);

}

int main()

{

	scanf("%d%d%d", &n, &k, &C);

	for(int i = 1; i <= n; i++) read(t[i]);

	sort(t + 1, t + n + 1);

	int head = 1, tail = 1;

	for(int i = 1; i < k; i++) f[i] = INF;

	for(int i = k; i <= n; i++)

	{

		while (head < tail && slope(Q[head + 1], Q[head]) < t[i] * 2) head++;

		f[i] = C + f[Q[head]] + (t[i] - t[Q[head] + 1]) * (t[i] - t[Q[head] + 1]);

	 	while (head <= tail && t[Q[tail]] == t[i - k + 1])

    	        {

        	        if (f[i - k + 1] <= f[Q[tail]]) tail--;

        	        else break;

    	        }

		while (head < tail && slope(i - k + 1, Q[tail]) < slope(Q[tail], Q[tail - 1])) tail--;

		Q[++tail] = i - k + 1;

	}

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

}

巴特西

JZOJ 3479. 工作安排

\(\text{solution}\)

最新文章

热门文章