简单插头DP小结

因为独立插头还有最小表示法没有打过，独立插头没看懂，广义路径连看都没看过，所以这些不再本文的总结范围内。

去年学插头DP的时候还是很惧怕的，也只做了一题，还是按着课件对着标程打的。还好今年终于懂得原理了。其实打多了也变成模板了（当然每题的转移不一样）。

插头DP有下面的分类：

  • 按模型：多回路问题、单回路问题、简单路径问题、广义路径问题
  • 按表示方法：是否有插头、括号法（广义括号法）、最小表示法

插头DP最朴素的实现就是用f[i][j][k]记下在(i, j)这个点轮廓线状态为k的答案。空间上很大，所以一般用队列实现了。而且队列实现可以免去动规数组初始化的麻烦。队列实现需要一个hash，对于内存比较宽裕的题目，可以直接开一个桶解决。

参考资料

多回路问题

这类问题是最水的，只要记录当前位置有没有插头即可。比如说hdu1693。

  • 有上插头和左插头 → 没有右插头或下插头
  • 没有上插头或做插头 → 有右插头和下插头
  • 只有一个插头 → 右插头和下插头分别只有一个

单回路问题

这类问题得维护连通性使得只存在一个联通快。具体的做法课件上讲的很清楚。例题有：

  • ural1519 Formula 1
  • poj1739 （如果在外面加一圈障碍的话，就变成上面那题了）
  • bzoj1187 （这题允许任意起点，并且不要求遍历全图）

限制起点终点的简单路径问题

简单路径问题按理来说应该用独立插头来解决，但是这类问题因为限制了起点和终点，所以比较好解决，只要对每个格子的类型进行判断，根据不同的格子进行不同的转移即可。比如说：

  • poj3133 （这题网上都说是独立插头，但是直接特判格子就可以过掉了）
  • poj1739 （这题如果不加一圈的话，用特判的方法还是很好写的）

hdu1693 代码

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

const int MAXN = 12;
int Testcase, n, m, map[MAXN][MAXN];
long long f[MAXN][MAXN][1<<MAXN];
long long solve()
{
  memset(f, 0, sizeof(f));
  scanf("%d%d", &n, &m);
  const int full = 1<<(m+1);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      scanf("%d", &map[i][j]);
  f[0][0][0] = 1;
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < m; ++j)
      for (int k = 0; k < full; ++k)
      {
        const int up = k & (1 << j);
        const int left = k & (1 << m);
        const int u = 1 << j, l = 1 << m;
        if (!map[i][j])
        {
          if (!up && !left)
            f[i][j+1][k] += f[i][j][k];
          continue;
        }

        if (up && left)
          f[i][j+1][k - u - l] += f[i][j][k];
        else if (!up && !left)
          f[i][j+1][k + u + l] += f[i][j][k];
        else if (up)
        {
          f[i][j+1][k] += f[i][j][k];
          f[i][j+1][k - u + l] += f[i][j][k];
        }
        else //if (left)
        {
          f[i][j+1][k] += f[i][j][k];
          f[i][j+1][k - l + u] += f[i][j][k];
        }
      }
    for (int k = 0; k < full/2; ++k)
      f[i+1][0][k] = f[i][m][k];
  }
  return f[n][0][0];
}
int main()
{
  scanf("%d", &Testcase);
  for (int i = 1; i <= Testcase; ++i)
    printf("Case %d: There are %I64d ways to eat the trees.\n", i, solve());
}

ural1519 代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

#include <cstdio>
#include <cstring>
#include <algorithm>

int pow3[13] = {1};
inline int get(const int x, const int j) { return x/pow3[j]%3; }
inline int set(const int x, const int j, const int value) { return x + (-get(x, j) + value) * pow3[j]; }
struct QueueNode
{
  int opt;
  long long sum;
} Q[2][13944];
int n, m, last, j, now, tail[2], pos[2][1594323];
char map[13][13];
int change1(const int opt, int i)
{
  for (int stack = 0; i < m; ++i)
  {
    const int tmp = get(opt, i);
    if (tmp == 1) ++stack;
    else if (tmp == 2) --stack;
    if (!stack)
      return set(opt, i, 1);
  }
  return -1;
}
int change2(const int opt, int i)
{
  for (int stack = 0; i >= 0; --i)
  {
    const int tmp = get(opt, i);
    if (tmp == 2) ++stack;
    else if (tmp == 1) --stack;
    if (!stack)
      return set(opt, i, 2);
  }
  return -1;
}
void enqueue(const int opt, const long long sum)
{
  if (j == m-1 && get(opt, m)) return;
  int& idx = pos[now][opt];
  if (idx)
    Q[now][idx].sum += sum;
  else
  {
    idx = ++tail[now];
    Q[now][idx].opt = opt;
    Q[now][idx].sum = sum;
  }
}
int main()
{
  for (int i = 1; i <= 12; ++i) pow3[i] = pow3[i-1]*3;

  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i)
  {
    scanf("\n%s", map[i]);
    for (int j = 0; j < m; ++j)
      if (map[i][j] == '.')
        last = i * m + j;
  }
  enqueue(0, 1);
  now ^= 1;
  for (int i = 0; i < n; ++i)
    for (j = 0; j < m; ++j)
    {
      for (int head = 1, t = tail[now^1]; head <= t; ++head)
      {
        const int opt = Q[now^1][head].opt;
        const long long sum = Q[now^1][head].sum;
        const int left = get(opt, m), up = get(opt, j);
        if (map[i][j] == '*')
        {
          if (left == 0 && up == 0)
            enqueue(opt, sum);
          continue;
        }
        if (left == 0 && up == 0)
          enqueue(set(set(opt, m, 2), j, 1), sum);
        else if (left == 2 && up == 1)
          enqueue(set(set(opt, m, 0), j, 0), sum);
        else if (left == 0 || up == 0)
        {
          enqueue(set(set(opt, m, 0), j, left+up), sum);
          enqueue(set(set(opt, j, 0), m, left+up), sum);
        }
        else if (left == 1 && up == 1)
        {
          const int tmp = change1(opt, j);
          enqueue(set(set(tmp, m, 0), j, 0), sum);
        }
        else if (left == 2 && up == 2)
        {
          const int tmp = change2(opt, j);
          enqueue(set(set(tmp, m, 0), j, 0), sum);
        }
        else if (left == 1 && up == 2)
        {
          if (i*m+j == last)
            enqueue(set(set(opt, m, 0), j, 0), sum);
        }
      }
      now ^= 1;
      for (int head = 1, t = tail[now]; head <= t; ++head)
        pos[now][Q[now][head].opt] = 0;
      tail[now] = 0;
    }
  printf("%I64d\n", Q[now^1][pos[now^1][0]].sum);
}

bzoj1187 代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include <cstdio>
#include <cstring>
#include <algorithm>

inline int get(const int x, const int j) { return (x >> (2*j)) & 3; }
inline int set(const int x, const int j, const int value) { return x + ((-get(x, j) + value) << (2*j)); }
const int MAXN = 6;
struct QueueNode
{
  int opt, sum;
} Q[2][1<<(2*MAXN)];
int n, m, j, now, pos[2][1<<(2*MAXN+2)], tail[2], a[100][6];
void enqueue(const int opt, const int sum)
{
  if (j == m-1 && get(opt, m)) return;
  int &idx = pos[now][opt];
  if (idx)
    Q[now][idx].sum = std::max(Q[now][idx].sum, sum);
  else
  {
    idx = ++tail[now];
    Q[now][idx].opt = opt;
    Q[now][idx].sum = sum;
  }
}
int change1(const int opt, int i)
{
  for (int stack = 0; i < m; ++i)
  {
    const int tmp = get(opt, i);
    if (tmp == 1) ++stack;
    else if (tmp == 2) --stack;
    if (!stack)
      return set(opt, i, 1);
  }
  return -1;
}
int change2(const int opt, int i)
{
  for (int stack = 0; i >= 0; --i)
  {
    const int tmp = get(opt, i);
    if (tmp == 2) ++stack;
    else if (tmp == 1) --stack;
    if (!stack)
      return set(opt, i, 2);
  }
  return -1;
}

int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      scanf("%d", &a[i][j]);
  enqueue(0, 0);
  now ^= 1;
  int ans = static_cast<int>(0x80000000UL);
  for (int i = 0; i < n; ++i)
    for (j = 0; j < m; ++j)
    {
      for (int head = 1, t = tail[now^1]; head <= t; ++head)
      {
        const int opt = Q[now^1][head].opt;
        const int sum = Q[now^1][head].sum;
        const int up = get(opt, j), left = get(opt, m);
        if (up == 0 && left == 0)
        {
          enqueue(set(set(opt, j, 1), m, 2), sum + a[i][j]);
          enqueue(opt, sum);
        }
        else if (up == 1 && left == 2)
          enqueue(set(set(opt,j, 0), m, 0), sum + a[i][j]);
        else if (up == 0 || left == 0)
        {
          enqueue(set(set(opt, j, 0), m, up+left), sum+a[i][j]);
          enqueue(set(set(opt, m, 0), j, up+left), sum+a[i][j]);
        }
        else if (up == 1 && left == 1)
        {
          const int tmp = change1(opt, j);
          enqueue(set(set(tmp, j, 0), m, 0), sum + a[i][j]);
        }
        else if (up == 2 && left == 2)
        {
          const int tmp = change2(opt, j);
          enqueue(set(set(tmp, j, 0), m, 0), sum + a[i][j]);
        }
        else if (up == 2 && left == 1)
        {
          if (set(set(opt, j, 0), m, 0) == 0)
            ans = std::max(ans, sum+a[i][j]);
        }
      }
      now ^= 1;
      for (int head = 1; head <= tail[now]; ++head)
        pos[now][Q[now][head].opt] = 0;
      tail[now] = 0;
    }
  printf("%d\n", ans);
}

poj3133 代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 10;
inline int get(const int x, const int j) { return (x >> (2*j)) & 3; }
inline int set(const int x, const int j, const int value)
  { return x + ((-get(x, j) + value) << (2*j)); }
struct QueueNode { int opt, dist; };
QueueNode Q[2][1<<(2*MAXN)];
int now, j, tail[2], n, m, map[MAXN][MAXN], pos[2][1<<(2*MAXN)];
void Enqueue(const int opt, const int dist)
{
  if (j == m-1 && get(opt, m))
    return;
  int &idx = pos[now][opt];
  if (idx)
    Q[now][idx].dist = std::min(Q[now][idx].dist, dist);
  else
  {
    idx = ++tail[now];
    Q[now][idx].opt = opt;
    Q[now][idx].dist = dist;
  }
}
int solve()
{
  now ^= 1;
  for (int head = 1, t = tail[now]; head <= t; ++head)
    pos[now][Q[now][head].opt] = 0;
  tail[0] = tail[1] = now = 0;

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      scanf("%d", &map[i][j]);

  Enqueue(0, 0);
  now ^= 1;
  for (int i = 0; i < n; ++i)
    for (j = 0; j < m; ++j)
    {
      for (int head = 1, t = tail[now^1]; head <= t; ++head)
      {
        const int opt = Q[now^1][head].opt;
        const int dist = Q[now^1][head].dist;
        const int up = get(opt, j), left = get(opt, m);

        if (map[i][j] == 0)
        {
          if (up+left == 0)
          {
            Enqueue(opt, dist);
            Enqueue(set(set(opt, j, 2), m, 2), dist+1);
            Enqueue(set(set(opt, j, 3), m, 3), dist+1);
          }
          else if (up+left == 2 || up+left == 3)
          {
            Enqueue(set(set(opt, j, up+left), m, 0), dist+1);
            Enqueue(set(set(opt, m, up+left), j, 0), dist+1);
          }
          else if (up == left)
            Enqueue(set(set(opt, j, 0), m, 0), dist+1);
        }
        else if (map[i][j] == 1)
        {
          if (up+left == 0)
            Enqueue(opt, dist);
        }
        else if (map[i][j] == 2 || map[i][j] == 3)
        {
          if (up+left == 0)
          {
            Enqueue(set(opt, j, map[i][j]), dist+1);
            Enqueue(set(opt, m, map[i][j]), dist+1);
          }
          else if (up+left == map[i][j])
            Enqueue(set(set(opt, j, 0), m, 0), dist+1);
        }
      }
      now ^= 1;
      for (int head = 1, t = tail[now]; head <= t; ++head)
        pos[now][Q[now][head].opt] = 0;
      tail[now] = 0;
    }
  return Q[now^1][pos[now^1][0]].dist;
}
int main()
{
  while (scanf("%d%d", &n, &m) != EOF && (n || m))
  {
    const int ans = solve()-2;
    printf("%d\n", ans == -2 ? 0 : ans);
  }
}

Comments