大家好，又见面了，我是全栈君。
题目大意：
给出一个序列x，从左边或者右边删数，使得总价值最大。
删除从i位置到k位置上的所有的数。操作价值为|xi – xk|*(k-i+1)，如果只删除一个数，操作价值为这个数的值。
解题思路：
区间dp
动态转移方程为：
f[i][j]=max(f[i][k]+f[k+1][j],f[i][j]);(f[i][j]=删除i到j的最大价值)f[i][j]=max(f[i][k]+f[k+1][j],f[i][j]);(f[i][j]=删除i到j的最大价值)
首先f[i][i]肯定是它本身 然后用（|xi — xk|×(k-i+1)）求出f[i][j] 的值， (n≥j＞i)
最后枚举一下就可以了
源程序：
#include<cstdio>
#include<algorithm>
using namespace std;
int ak,n,a[105],f[105][105];
int main()
{
//freopen("remove.in","r",stdin);
//freopen("remove.out","w",stdout);
int o=0;
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&f[i][i]);
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++)
f[i][j]=abs(f[j][j]-f[i][i])*(j-i+1);//初始化
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)
for (int k=i;k<j;k++)//枚举删除范围
f[i][j]=max(f[i][k]+f[k+1][j],f[i][j]);//取最大价值
printf("%d",f[1][n]);//愉快输出
}转载于:https://www.cnblogs.com/Juruo-HJQ/p/9308681.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107628.html原文链接：https://javaforall.net
