Description 小明现在有 n 个不同的正整数 X1 ， X2 ， … Xn 排成一行。 小明每次可以将左边或右边删掉连续的若干个数（只能从两边删数 ） 。 每次删数可以得到一个值，若删除从 i 到 j 的数 i xiaoyu j 则得到的价值为 |Xi-Xj|*（ j-i+1 ） 。 若只删除一个数（ i=j ） ，则得到的价值为 Xi 。 现在小明想使得到的价值总和最大，请你帮他计算一下，这个最大值是多少？ Input 第一行一个整数 n 。 第二行 n 个整数，表示 X 。 Output 输出仅一行一个整数，表示能得到的最大价值。 Sample Input 6 54 29 196 21 133 118 Sample Output 768 Data Constraint Hint 对于 30% 的数据满足 1 ≤ n ≤ 100 。 对于 100% 的数据满足 1 ≤ n ≤ 2,000 。
简单Dp，设F[i]为删掉i个数后的总价值，转移很简单，随便搞搞就好了。
#include <cstdio> #include <iostream> #include <algorithm> #define N 2005 #define fo(i,a,b) for (int i=a;i<=b;i++) using namespace std; int F[N],a[N]; int main() { int n; scanf("%d",&n); F[0]=0; fo(i,1,n) { scanf("%d",&a[i]); F[i] = F[i - 1] + a[i]; fo(j,0,i-2) F[i] = max(F[i],F[j] + abs(a[i] - a[j+1]) * (i-j)); } printf("%d",F[n]); }