『数组的最大代价贪心优化DP』

<更新提示>

<第一次更新>

<正文>

数组的最大代价(51nod 1270)

Description

数组A包含N个元素A1, A2......AN。数组B包含N个元素B1, B2......BN。并且数组A中的每一个元素Ai，都满足1 <= Ai <= Bi。数组A的代价定义如下：

\[S=\sum_{i=2}^{N}|A_i-A_{i-1}|
\]

（公式表示所有两个相邻元素的差的绝对值之和）

给出数组B，计算可能的最大代价S。

Input Format

第1行：1个数N，表示数组的长度(1 <= N <= 50000)。

第2 - N+1行：每行1个数，对应数组元素Bi(1 <= Bi <= 10000)。

Output Format

输出最大代价S。

Sample Input

Sample Output

解析

化简题目大意可以得知：即求一个数组限制下的相邻两项最大差值和。

有一个很简单的暴力DP思路如下：

设\(f[i][j]\)代表前\(i\)项当中，第\(i\)个数字取\(j\)的最大和。

\(f[i][j]=max\{f[i-1][k]+|j-k|\}\)

\((i=1 - n,j=1 - B_i,k=1 - B_{i-1})\)

时间复杂度\(O(nMax\{b_i\}^2)\)

不怕暴力TLE，就怕暴力不敢想。没错，最简单的暴力就是这道题的关键。

我们可以用贪心对这个暴力进行降维打击优化。

最显然的贪心，构造\(A_i\)时极端化能得到全局最优解。即：\(A_i\)的最优取值方案只有两种可能，\(1\)或\(B_i\)，这样可以让相邻两项的差的绝对值尽可能大。

那么\(j\)，\(k\)都只能取最大值或\(1\)，直接实现\(O(1)\)转移。可以优化一下状态：设\(f[i][0/1]\)代表前\(i\)项当中，第\(i\)个数字取\(1\)(第二维为0)或\(B_i\)(第二维为1)的最大和。

状态转移方程：

\[f[i][0]=max(f[i-1][0],f[i-1][1]+|B_{i-1}-1|)\\f[i][1]=max(f[i-1][0]+|B_i-1|,f[i-1][1]+|B_i-B_{i-1}|)
\]

可以滚动数组一下把第一维的空间也优化了。

\(Code:\)

#include<bits/stdc++.h>

using namespace std;

inline void read(int &k)

{

	int w=0,x=0;char ch;

	while(!isdigit(ch))w|=ch=='-',ch=getchar();

	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();

	k=(w?-x:x);return;

}

const int N=50000+80;

int n,b[N],f[2][2];

inline void input(void)

{

	read(n);

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

}

inline void dp(void)

{

	f[1][0]=f[1][1]=0;

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

	{

		f[i&1][0]=max(f[i-1&1][0],f[i-1&1][1]+abs(b[i-1]-1));

		f[i&1][1]=max(f[i-1&1][0]+abs(b[i]-1),f[i-1&1][1]+abs(b[i]-b[i-1]));

	}

}

int main(void)

{

	input();

	dp();

	printf("%d\n",max(f[n&1][0],f[n&1][1]));

}

考点：算法思想的结合运用。

<后记>