[Codeforces1013E] Hills(DP)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/1013/problem/E

给n个数，允许让每个数删减，现想要求k个严格的局部最大值，k取值为$[1,\lceil\frac{n}{2}\rceil]$。

这dp考的时候没想出来，可以这么做：$f(i,j,k)$表示前$i$个数里有$j$个最大值，此时还讨论第$i$个数是($k=1$)否($k=0$)是局部最大值。

状态转移如下：

img

$k=0$时，$f(i,j,0)$可以更新到$f(i+1,j,0)$上，因为此时$i$和$i+1$都不是局部最大值，因此$j$不会变；或者更新到$f(i+1,j+1,1)$上，此时在$i+1$处为一个局部最大值。

$k=1$时，$f(i,k,1)$更新到$f(i+1,j,0)$上，但是相应地要有删减的代价；也可以更新到$f(i+2,j+1,1)$上，显然$i+1$处必然是一个极小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5050;
const int inf = 0x7f7f7f7f;
int n;
int a[maxn];
int f[maxn][maxn][2];

int update(int x, int y) {
  return x > y ? 0 : y - x + 1;
}

int main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d",&n)) {
    for(int i = 1; i <= n; i++) {
      scanf("%d",&a[i]);
    }
    int K = (int)ceil(n / 2.0);
    memset(f, 0x7f, sizeof(f));
    f[1][0][0] = 0; f[1][1][1] = 0;
    for(int i = 1; i <= n; i++) {
      for(int j = 0; j <= K; j++) {
        for(int k = 0; k <= 1; k++) {
          if(f[i][j][k] == inf) continue;
          if(k == 0) {
            f[i+1][j+1][1] = min(f[i+1][j+1][1], f[i][j][k] + update(a[i+1], a[i]));
            f[i+1][j][0] = min(f[i+1][j][0], f[i][j][k]);
          }
          else {
            f[i+2][j+1][1] = min(f[i+2][j+1][1], f[i][j][k] + update(min(a[i], a[i+2]), a[i+1]));
            f[i+1][j][0] = min(f[i+1][j][0], f[i][j][k] + update(a[i], a[i+1]));
          }
        }
      }
    }
    for(int i = 1; i <= K; i++) {
      printf("%d%c", min(f[n][i][0], f[n][i][1]), " \n"[i==K]);
    }
  }
  return 0;
}