删數_紀中3097_dp

Description

小明現在有 n 個不同的正整數 X1 ， X2 ， … Xn 排成一行。

小明每次可以将左邊或右邊删掉連續的若幹個數（隻能從兩邊删數 ） 。

每次删數可以得到一個值，若删除從 i 到 j 的數（ i < j ） ，則得到的價值為 |Xi-Xj|*

（ j-i+1 ） 。

若隻删除一個數（ i=j ） ，則得到的價值為 Xi 。

現在小明想使得到的價值總和最大，請你幫他計算一下，這個最大值是多少？

Input

第一行一個整數 n 。

第二行 n 個整數，表示 X 。

Output

輸出僅一行一個整數，表示能得到的最大價值。

Hint

對于 30% 的資料滿足 1 ≤ n ≤ 100

對于 100% 的資料滿足 1 ≤ n ≤ 2,000

題解

因為從左删和從右删都是一樣的，是以直接從左往右取

等同于求将n個數字分成若幹組的最大價值

f [ i ] f[i] f[i]表示前i項的最大獲益

f [ i ] = m a x ( f [ j − 1 ] + ∣ a [ j ] − a [ i ] ∣ ∗ ( i − j + 1 ) ) f[i]=max(f[j-1]+\left|a[j]-a[i]\right|*(i-j+1)) f[i]=max(f[j−1]+∣a[j]−a[i]∣∗(i−j+1))

f [ i ] = m a x ( f [ i ] , f [ i − 1 ] + a [ i ] ) f[i]=max(f[i],f[i-1]+a[i]) f[i]=max(f[i],f[i−1]+a[i])

Code

#include <stdio.h>
#include <cmath>
using namespace std;
int f[2001];
int a[2001];
int max(int x,int y)
{
	return x<y?y:x;
}
int main()
{
	int n,ans=0;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		 scanf("%d",&a[i]);
	f[1]=a[1];
	for (int i=2;i<=n;i++)
	{
		for (int b=1;b<=i-1;b++)
			f[i]=max(f[b-1]+abs(a[b]-a[i])*(i-b+1),f[i]);
		f[i]=max(f[i-1]+a[i],f[i]);
	}
	printf("%d\n",f[n]);
	return 0;
}