P2426 删数

P2426 删数

题目分析

由于对于题目所得的最优删法，与删除的顺序无关，因此我们可以默认从前往后删片段。

设 \(dp_i\) 表示删除前 \(i\) 个数所得到的最大价值。

对于第 \(i\) 个数，它可以选择独自删除 \(i\) 。状态转移方程为

$ dp_i $ \(=\) $ dp_{i-1}$ \(+\) \(a_i\) 。

亦可以选择与前面的数一起删掉。求此时与哪几个数一起删得最大值。

\(dp_i\) \(=\) $dp_{j-1} + $$abs (a_i-a_j)*(i-j+1)$ \((1\le j < i)\)

表示删除 \(j-i\) 段的数。

code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[105],dp[105];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dp[1]=a[1]; 
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			dp[i]=max(dp[i],dp[j-1]+abs(a[i]-a[j])*(i-j+1));
		}
		dp[i]=max(dp[i],dp[i-1]+a[i]);
	}
	cout<<dp[n]<<endl;
	return 0;
} 

summary

今天这题看似很简单，想明白却不容易。

本来一开始定义的是 \(dp_{i,j}\) 表示删除 \(i-j\) 段所获得的最大价值。

但接下来就遇到难点了，我们要如何枚举断点 \(k\) 。

如果只是将断点 \(k\) 看做将 \(i-j\) 字符分成两端所得到的最大价值，那可出大问题了。

对于一段字符，它的最优断法不一定是断成两段。

但是，若断点\(k\)表示其中有一段删除的是\(k-j\),而删除\(i-(k-1)\) 段所获得的最大价值为 \(dp_{i,k-1}\) 。这...状态转移方程不就又出来了。

至此，根本思路与题目分析已无差别。

因此，在思考问题时，一定要注意从问题本身出发，来找状态转移方程。

作者的话

\(dp\)百道第\(5\)题,感觉得到对\(dp\)是有帮助的。

加油加油加油！

-\(End\)-

\(2023.1.2\)