题解 洛谷 P2885 [USACO07NOV]Telephone Wire G

1. 题面描述

题目链接

给出 \(n\) 棵树的高度。

你可以进行任意次操作，每次操作形如：把某棵树增高 \(x\)，代价为 \(x^2\)（注意：不能将一棵树的高度减少）。

在操作完之后，一个状态的代价定义为相邻两树高度差的和 \(\times c\)。

求最小代价。

\(n\le 10^5\)，\(a[i],x\le 100\)，其中 \(a[i]\) 表示第 \(i\) 棵树的高度。

2. 分析

考虑 DP。

设 \(f[i][j]\) 表示操作完前 \(i\) 棵树，其中第 \(i\) 棵树的高度为 \(j\) 时的最小代价。于是状态转移方程：

\(f[i][j]=min_{k\ge a[i-1]}\{f[i-1][k]+c\times \left|j-k\right|\}+(j-a[i])^2,~~j\ge a[i]\)。

初值 \(f[1][i]=(i-a[1])^2,~~i\ge a[1]\)。

答案 \(ans=min\{f[n][i]\}\)。

时间复杂度 \(O(n\times max(a[i])^2)\)

考虑优化。

先把绝对值拆开。于是状态转移方程：

\(f[i][j]= \begin{cases} min_{k\ge a[i-1]}\{f[i-1][k]+c\times (j-k)\}+(j-a[i])^2,~j\ge k\\ min_{k\ge a[i-1]}\{f[i-1][k]+c\times (k-j)\}+(j-a[i])^2,~j<k\\ \end{cases},~~j\ge a[i]\)

整理，得：

\(f[i][j]= \begin{cases} min_{k\ge a[i-1]}\{f[i-1][k]-c\times k)\}+c\times j+(j-a_i)^2,~j\ge k\\ min_{k\ge a[i-1]}\{f[i-1][k]+c\times k)\}-c\times j+(j-a_i)^2,~j<k\\ \end{cases},~~j\ge a[i]\)

因为两个式子条件不一样，于是考虑分别处理，首先观察第一个式子：

\(f[i][j]=min_{k\ge a[i-1]}\{f[i-1][k]-c\times k)\}+c\times j+(j-a_i)^2,~~j\ge k~\&\&~j\ge a[i]\)

发现 \(k\) 的取值范围随着 \(j\) 的递增而增大，并且左端点固定，于是考虑在转移时使用一个变量来维护合法的 \(k\) 的最大值。

观察第二个式子：

\(f[i][j]=min_{k\ge a[i-1]}\{f[i-1][k]+c\times k)\}-c\times j+(j-a_i)^2,~~j<k~\&\&~j\ge a[i]\)

发现 \(k\) 的取值范围随着 \(j\) 的递减而增大，并且右端点固定为上界，于是考虑使用一个变量来维护合法的 \(k\) 的最大值。

这时时间复杂度就被优化为了 \(O(n\times max(a[i]))\)。

注意转移时循环的上下界，因为上述式子中的 \(j\) 和 \(k\) 都有取值范围的限制。

3. 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,W=105;
const ll inf=0x3f3f3f3f3f3f3f3f;

int n,c;
int a[N];
ll f[N][W];

inline ll sq(ll x) {return 1ll*x*x;}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>c;
	for (int i=1; i<=n; i++) cin>>a[i];
	memset(f,0x3f,sizeof f);
	for (int i=a[1]; i<=100; i++) f[1][i]=sq(i-a[1]);
	for (int i=2; i<=n; i++) {
		ll minn=inf;
		for (int j=a[i-1]; j<=100; j++) {
			minn=min(minn,f[i-1][j]-1ll*c*j);
			if (j>=a[i]) f[i][j]=minn+1ll*c*j+sq(j-a[i]);
		}
		minn=inf;
		for (int j=100; j>=a[i]; j--) {
			f[i][j]=min(f[i][j],minn-1ll*c*j+sq(j-a[i]));
			if (j>=a[i-1]) minn=min(minn,f[i-1][j]+1ll*c*j);
		}
	}
	ll ans=inf;
	for (int i=1; i<=100; i++) ans=min(ans,f[n][i]);
	cout<<ans<<'\n';
	return 0;
}

本文完。