环形石子合并

1068. 环形石子合并

对于环形 DP 问题，一种通用的处理环形的方式是，将原数组复制一份再接到后面，然后再按照区间 DP 的做法来解。

1
2
3
4
for 区间长度 len: 1 ~ n
  for 左端点 l: 1 ~ l + len - 1
    r = l + len - 1
    for 分界点 k

f[l][r] 状态表示的集合：将 l ~ r 堆的石子合并成一堆的所有方案，属性：花费力气的最小值

集合划分依据：将区间 l 到 r 的所有石子合并成一堆，最后一次合并发生的位置 k

状态转移方程：f[l][r] = min{f[l][k] + f[k + 1][r] + s[r] - s[l - 1]}，其中 k = 1, 2, …, r - 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
44
#include <cstring>
#include <iostream>
using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

int n;
int s[N], w[N];
int f[N][N], g[N][N];

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    w[i + n] = w[i];
  }
  for (int i = 1; i <= n * 2; i++) {
    s[i] = s[i - 1] + w[i];
  }
  memset(f, 0x3f, sizeof f);
  memset(g, -0x3f, sizeof g);

  for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n * 2; l++) {
      int r = l + len - 1;
      if (len == 1) {
        f[l][r] = g[l][r] = 0;
      } else {
        for (int k = 1; k < r; k++) {
          f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
          g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
        }
      }
    }
  }
  // 最后处理环形
  int minv = INF, maxv = -INF;
  for (int i = 1; i <= n; i++) {
    minv = min(minv, f[i][i + n - 1]);
    maxv = max(maxv, g[i][i + n - 1]);
  }
  cout << minv << endl << maxv << endl;
  return 0;
}

能量项链

320. 能量项链

能量项链区间 DP 分析

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
#include <cstring>
#include <iostream>

using namespace std;

const int N = 210;

int n;
int w[N];
int f[N][N];

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    w[i + n] = w[i];
  }
  // 枚举区间长度，从 3 开始，对应两个珠子的情况。假设输入为 2 3 5 10，我们实际要处理的是 2 3 5 10 2，所以 n + 1
  for (int len = 3; len <= n + 1; len++) {
    // 枚举左端点
    for (int l = 1; l + len - 1 <= n * 2; l++) {
      int r = l + len - 1;
      // 枚举分界点. 分界点对应两个珠子之间，我们存的是 2 3 5 10 2，中间的 3 5 10 都是共用的，可以代表分界点，k 取第 1 个位置和最后一个位置没意义
      for (int k = l + 1; k < r; k++) {
        f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
      }
    }
  }
  // 处理环形问题
  int res = 0;
  for (int i = 1; i <= n; i++) {
    res = max(res, f[i][i + n]);
  }
  cout << res << endl;
  return 0;
}

凸多边形划分

1069. 凸多边形的划分

区间 DP 和高精度计算的结合

凸多边形划分区间 DP 分析

朴素不带高精度版：

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
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 55, M = 35, INF = 2e9;

int n;
int w[N];
int f[N][N];

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> w[i];
  for (int len = 3; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
      int r = l + len - 1;
      f[l][r] = INF;
      for (int k = l + 1; k < r; k++) {
        f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
      }
    }
  }
  cout << f[1][n] << endl;
  return 0;
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 55, M = 35, INF = 2e9;

int n;
int w[N];
LL f[N][N][M]; // 其中 M 是位数，用来存数字的每一位

// 高精度加法
void add(LL a[], LL b[]) {
  // 辅助数组
  static LL c[M];
  memset(c, 0, sizeof c);
  for (int i = 0, t = 0; i < M; i++) {
    t += a[i] + b[i];
    c[i] = t % 10;
    t /= 10;
  }
  memcpy(a, c, sizeof c);
}

// 高精度乘法
void mul(LL a[], LL b) {
  static LL c[M];
  memset(c, 0, sizeof c);
  LL t = 0;
  for (int i = 0; i < M; i++) {
    t += a[i] * b; // 这一行和加法不同
    c[i] = t % 10;
    t /= 10;
  }
  memcpy(a, c, sizeof c);
}

int cmp(LL a[], LL b[]) {
  for (int i = M; i >= 0; i--) {
    if (a[i] > b[i])
      return 1;
    else if (a[i] < b[i])
      return -1;
  }
  return 0;
}

void print(LL a[]) {
  int k = M - 1;
  while (k && !a[k]) k--;
  while (k >= 0) cout << a[k--];
  cout << endl;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> w[i];
  LL temp[M];
  for (int len = 3; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
      int r = l + len - 1;
      f[l][r][M - 1] = 1;
      for (int k = l + 1; k < r; k++) {
        memset(temp, 0, sizeof temp);
        temp[0] = w[l];
        mul(temp, w[k]);
        mul(temp, w[r]);
        add(temp, f[l][k]);
        add(temp, f[k][r]);
        if (cmp(f[l][r], temp) > 0) {
          memcpy(f[l][r], temp, sizeof temp);
        }
      }
    }
  }
  print(f[1][n]);
  return 0;
}

加分二叉树

479. 加分二叉树

加分二叉树区间 DP 分析

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
#include <iostream>
using namespace std;

int n;
const int N = 35;
int w[N];
int f[N][N], g[N][N];

void dfs(int l, int r) {
  if(l > r) return;
  int root = g[l][r];
  cout << root << ' ';
  dfs(l, root - 1);
  dfs(root +1, r);
}

int main() {
  cin >> n;
  for(int i=1;i<=n;i++) cin >> w[i];
  for(int len=1;len<=n;len++) {
    for(int l=1;l+len-1<=n;l++) {
      int r = l + len -1;
      if(len == 1) {
        f[l][r] = w[l];
        g[l][r] = l;
      } else {
        for(int k=l;k<=r;k++) {
          int left = k == l ? 1 : f[l][k-1];
          int right = k == r ? 1 : f[k+1][r];
          int score = left * right + w[k];
          if(f[l][r] < score) {
            f[l][r] = score;
            g[l][r] = k;
          }
        }
      }
    }
  }
  cout << f[1][n] << endl;
  dfs(1, n);
  return 0;
}

棋盘分割

321. 棋盘分割

棋盘分割区间 DP 分析

注意本题的切割方式，切完一刀之后，只能选一块继续切，另一块不能再切了。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cmath>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 15, M = 9;
const double INF = 1e9;

int n, m = 8;
int s[M][M];
double f[M][M][M][M][N];
double X;

int get_sum(int x1, int y1, int x2, int y2) {
  return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

double get(int x1, int y1, int x2, int y2) {
  double sum = get_sum(x1, y1, x2, y2) - X;
  return (double)sum * sum / n;
}

double dp(int x1, int y1, int x2, int y2, int k) {
  double &v = f[x1][y1][x2][y2][k];
  if (v >= 0) return v;
  if (k == 1) return v = get(x1, y1, x2, y2);
  v = INF;
  // 横着切
  for (int i = x1; i < x2; i++) {
    // 保留上面，继续切下面
    v = min(v, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));
    // 保留下面，继续切上面
    v = min(v, get(i + 1, y1, x2, y2) + dp(x1, y1, i, y2, k - 1));
  }
  // 竖着切
  for (int i = y1; i < y2; i++) {
    // 保留左边，继续切右边
    v = min(v, get(x1, y1, x2, i) + dp(x1, i + 1, x2, y2, k - 1));
    v = min(v, get(x1, i + 1, x2, y2) + dp(x1, y1, x2, i, k - 1));
  }
  return v;
}

int main() {
  cin >> n;
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> s[i][j];
      s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
  }
  X = (double)s[m][m] / n;
  memset(f, -1, sizeof f);
  printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, n)));
  return 0;
}