状态压缩 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstring>
#include <iostream>

using namespace std;
const int N = 12, M = 1 << N;

int n, m;
// f[i][j] 表示 1 x 2 长方形从 i-1 列捅到 i 列，且这种参差不齐的状态可以表示为 j 的所有方案数。j 看做一个二进制数，如果横着的长方形从 i-1 列捅到 i 列，该位记为 1，否则记为 0
long long f[N][M];
// st[i] 表示 i 这种状态是否合法，例如 (1010)2 这种状态 st[10] 不合法，因为这样的列中连续是空的格子的长度为奇数，无法被竖着的 2 x 1 长方形填满
bool st[M];

int main() {
  int n, m;
  while (cin >> n >> m, n || m) {
    memset(f, 0, sizeof f);
    // 先预处理处所有参差不齐的状态，那些合法，那些非法
    for (int i = 0; i < 1 << n; i++) {
      st[i] = true;
      int cnt = 0;
      for (int j = 0; j < n; j++) {
        if (i >> j & 1) {
          if (cnt & 1) st[i] = false;
          cnt = 0;
        } else
          cnt++;
      }
      if (cnt & 1) st[i] = false;
    }

    f[0][0] = 1;
    // 遍历每一列
    for (int i = 1; i <= m; i++) {
      // 遍历当前列上可能的参差不齐的状态
      for (int j = 0; j < 1 << n; j++) {
        // 遍历前一列上可能的参差不齐的状态
        for (int k = 0; k < 1 << n; k++) {
          // 转移条件：同一行上，前一列横着的长方形不能捅到当前列；上一列连续空的位置长度不能为奇数。当前列对应位置放没放对应 j 这个二进制状态，因为是 1 x 2 的长方形，所以上一列所有 j 对应的位置都是放着的，因此要 j | k 取并集
          if ((j & k) == 0 && st[j | k]) {
            f[i][j] += f[i - 1][k];
          }
        }
      }
    }
    cout << f[m][0] << endl;
  }
}

最短 Hamilton 路径

最短 Hamilton 路径 DP 分析

状态转移方程：f[i][j] = min(f[i - (1 << j)][k] + a[k][j])

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

using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> w[i][j];
    }
  }
  memset(f, 0x3f, sizeof f);
  f[1][0] = 0;
  for (int i = 0; i < 1 << n; i++) {
    for (int j = 0; j < n; j++) {
      if (i >> j & 1) {
        for (int k = 0; k < n; k++) {
          if ((i - (1 << j)) >> k & 1) {
            f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
          }
        }
      }
    }
  }
  cout << f[(1 << n) - 1][n - 1] << endl;
  return 0;
}

树形 DP

从根节点开始，递归求解每个节点。

没有上司的舞会

没有上司的舞会 DP 分析

状态计算：
f(u,0)=∑max(f(si,0),f(si,1))f(u, 0)=\sum max(f(s_i,0), f(s_i,1))
f(u,1)=∑f(si,0)f(u, 1)=\sum f(s_i, 0)

对于一个节点 u，如果不选 u，只从 u 的子树进行选择，对于每个 u 的孩子 sis_i，分别计算 f(si,0),f(si,1)f(s_i,0), f(s_i,1)，取最大值，然后累加，就是这种情况下的方案数。

如果选 u，那么不能选 u 的孩子，此时对于每个 u 的孩子 sis_i，计算 f(si,0)f(s_i,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
#include <cstring>
#include <iostream>
using namespace std;

const int N = 6010;

int n;
int happy[N];
// 邻接表存树
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];

void add(int a, int b) {
  e[idx] = b;
  ne[idx] = h[a];
  h[a] = idx++;
}
void dfs(int u) {
  f[u][1] = happy[u];
  for (int i = h[u]; i != -1; i = ne[i]) {
    int j = e[i];
    dfs(j);
    f[u][0] += max(f[j][0], f[j][1]);
    f[u][1] += f[j][0];
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &happy[i]);
  memset(h, -1, sizeof h);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    // 记录下当前节点是否有父亲，用于找出根节点
    has_father[a] = true;
    add(b, a);
  }
  int root = 1;
  // 没有父亲节点的节点就是树根
  while (has_father[root]) root++;
  // 从树根开始递归求解
  dfs(root);
  printf("%d\n", max(f[root][0], f[root][1]));
  return 0;
}

记忆化搜索

滑雪

滑雪 DP 分析

f[i][j] 表示所有从 (i, j) 开始滑的路径长度最大值，可以分为四类：

  1. 从 (i, j) 开始向上滑，f[i][j] = f[i-1][j] + 1
  2. 从 (i, j) 开始向右滑，f[i][j] = f[i][j+1] + 1
  3. 从 (i, j) 开始向下滑，f[i][j] = f[i+1][j] + 1
  4. 从 (i, j) 开始向左滑，f[i][j] = f[i][j-1] + 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
#include <cstring>
#include <iostream>
using namespace std;

const int N = 310;
int n, m;
int h[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y) {
  int &v = f[x][y];
  if (v != -1) return v;
  v = 1;
  for (int i = 0; i < 4; i++) {
    int a = x + dx[i], b = y + dy[i];
    if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y]) {
      v = max(v, dp(a, b) + 1);
    }
  }
  return v;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &h[i][j]);
    }
  }
  memset(f, -1, sizeof f);
  int res = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      res = max(res, dp(i, j));
    }
  }
  printf("%d\n", res);
  return 0;
}