题解 P2426 【删数】

柒命九陨_ · 2018-08-07 09:11:37 · 题解

是区间DP良心水题了qwq。

所以大家为什么都开的是二维数组呢，明明一维就好的。

题意唯一有干扰的是从后面删数的这个选择，但是稍微一想就知道每次从前面删数一直删到最后，最优解是不变的，最后留下的也是我们曾要从后面删去的区间。

所以从前向后更新就好了，dp[ i ] 表示删到第 i 个数时的最大值，j 枚举前面一起删去的区间长度。

代码如下qwq。

#include <cstdio>
#include <algorithm>
using namespace std;

int n, val[105], dp[105];

inline int Val(int l, int r) {
  return abs(val[l] - val[r]) * (r - l + 1);
}

int main(int argc, char const *argv[]) 
{
  // freopen("nanjolno.in", "r", stdin);
  // freopen("nanjolno.out", "w", stdout);

  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) scanf("%d", &val[i]);
  for(int i = 1; i <= n; ++i) {
    dp[i] = max(dp[i], dp[i - 1] + val[i]);
    for(int j = 2; j <= i; ++j)
      dp[i] = max(dp[i], dp[i - j] + Val(i - j + 1, i));
  }
  printf("%d\n", dp[n]);

  // fclose(stdin), fclose(stdout);
  return 0;
}