斜率优化板题 HDU2829 Lawrence

题目大意：给定一个长度为nnn的序列，至多将序列分成m+1m+1m+1段，每段序列都有权值，权值为序列内两个数两两相乘之和。求序列权值和最小为多少？
数据规模：m<=n<=1000.m<=n<=1000.m<=n<=1000.
分析：令w[i,j]w[i,j]w[i,j]表示区间[i,j][i,j][i,j]中两两乘积之和,f[i][j]f[i][j]f[i][j]表示前jjj个数分成iii段的最小值。

f[i][j]=f[i−1][k]+w[k+1,j]f[i][j]=f[i-1][k]+w[k+1,j]f[i][j]=f[i−1][k]+w[k+1,j]

w[k+1,j]w[k+1,j]w[k+1,j]可以转换为w[1,j]−w[1,k]−sum[k]∗(sum[j]−sum[k])w[1,j]-w[1,k]-sum[k]*(sum[j]-sum[k])w[1,j]−w[1,k]−sum[k]∗(sum[j]−sum[k])

其中sum[j]sum[j]sum[j]表示前j个数的前缀和。令w[i]=w[1,i]w[i]=w[1,i]w[i]=w[1,i]

f[i][j]=f[i−1][k]+w[j]−w[k]−sum[k]∗(sum[j]−sum[k])f[i][j]=f[i-1][k]+w[j]-w[k]-sum[k]*(sum[j]-sum[k])f[i][j]=f[i−1][k]+w[j]−w[k]−sum[k]∗(sum[j]−sum[k])

y=f[i−1][k]−w[k]+sum[k]2y=f[i-1][k]-w[k]+sum[k]^2y=f[i−1][k]−w[k]+sum[k]2

x=sum[k]x=sum[k]x=sum[k]

k=sum[j]k=sum[j]k=sum[j]

g=f[i][j]−w[j]g=f[i][j]-w[j]g=f[i][j]−w[j]

则有：y−kx=by-kx=by−kx=b

此为直线方程，kkk为定值，要求bbb(w[j]w[j]w[j]为定值)最小，即为直线的截距最小。平面上有若干点(x,y)(x,y)(x,y),这些点是由各个决策点产生的。而将直线从下往上平移，它接触到的第一个点即为最佳决策点。因为斜率bbb是上升的，所以，下一阶段的直线方程斜率更高，于是最佳决策点一定形成了下凸包序列。

还可以用滚动数组…具体见代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005;

#define LL long long

int n, m, s, t, dq[MAXN];

LL sum[MAXN], w[MAXN], f[2][MAXN];

inline LL Getup(int now, int i, int j) { return (f[now][i] + sum[i]*sum[i] - w[i]) - (f[now][j] + sum[j]*sum[j] - w[j]); }//Yi-Yj

inline LL Getdown(int now, int i, int j) { return sum[i] - sum[j]; }//Xi-Xj

int main ()

{

	int x;

	while(scanf("%d%d", &n, &m), n || m)

	{

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

			scanf("%d", &x), sum[i] = sum[i-1] + x, w[i] = w[i-1] + sum[i-1] * x;

		int now = 0;

		for(int i = 1; i <= n; i++) f[now][i] = w[i];

		for(int i = 2; i <= m+1; i++)

		{

			now ^= 1, s = t = 0, dq[t++] = 0;

			for(int j = 1; j <= n; j++)

			{

				while(t-s > 1 && Getup(now^1, dq[s+1], dq[s])  <= sum[j] * Getdown(now^1, dq[s+1], dq[s])) s++;

				f[now][j] = f[now^1][dq[s]] + w[j] - w[dq[s]] - sum[dq[s]] * (sum[j] - sum[dq[s]]);

				while(t-s > 1 && Getup(now^1, j, dq[t-1]) * Getdown(now^1, dq[t-1], dq[t-2]) <= Getup(now^1, dq[t-1], dq[t-2]) * Getdown(now^1, j, dq[t-1])) t--;

				dq[t++] = j;

			}

		}

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

	}

}

巴特西

斜率优化板题 HDU2829 Lawrence

最新文章

热门文章