状态压缩 DP

小国王

1064. 小国王

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n, m;
// state 记录所有合法状态
vector<int> state;
// cnt[i] 记录状态 i 中包含多少个 1
int cnt[M];
// head[i] 记录所有可以转移到状态 i 的状态
vector<int> head[M];
// DP 数组
LL f[N][K][M];

// 检查一个状态是不是合法状态
bool check(int state) {
  for (int i = 0; i < n; i++) {
    if ((state >> i & 1) && (state >> i + 1 & 1)) {
      return false;
    }
  }
  return true;
}

// 计算一个状态中 1 的个数
int count(int state) {
  int res = 0;
  for (int i = 0; i < n; i++) res += state >> i & 1;
  return res;
}

int main() {
  cin >> n >> m;
  // 将所有合法状态与处理出来，同时记录这个状态里包含多少个 1
  for (int i = 0; i < 1 << n; i++) {
    if (check(i)) {
      state.push_back(i);
      cnt[i] = count(i);
    }
  }
  // 两两比较每个状态，记录每个状态可以由哪些状态转移过来
  for (int i = 0; i < state.size(); i++) {
    for (int j = 0; j < state.size(); j++) {
      int a = state[i], b = state[j];
      if ((a & b) == 0 && check(a | b)) {
        head[i].push_back(j);
      }
    }
  }
  // 初始化，不摆任何国王也算一种摆法，所以初始化成 1
  f[0][0][0] = 1;
  // 枚举行数
  for (int i = 1; i <= n + 1; i++) {
  // 枚举摆了几个国王
    for (int j = 0; j <= m; j++) {
      // 枚举最后一行可能的状态
      for (int a = 0; a < state.size(); a++) {
        // 枚举所有可以转移到当前状态的那些状态，也就是 i-1 行的状态
        for (int b : head[a]) {
          int c = cnt[state[a]];
          if (j >= c) {
            // 最后一行摆的国王的数量不能超过当前考虑的国王数目
            f[i][j][a] += f[i - 1][j - c][b];
          }
        }
      }
    }
  }
  cout << f[n + 1][m][0] << endl;
  return 0;
}

玉米田

327. 玉米田

和上一题基本一样，这道题不同的地方是四连通和有的格子不能用。

#include <iostream>
#include <vector>
using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n, m;
int g[N];
vector<int> state;
vector<int> head[M];
int f[N][M];

bool check(int state) {
  for (int i = 0; i < m; i++) {
    if ((state >> i & 1) && (state >> i + 1 & 1)) {
      return false;
    }
  }
  return true;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      int t;
      cin >> t;
      g[i] += !t << j;
    }
  }
  for (int i = 0; i < 1 << m; i++) {
    if (check(i)) {
      state.push_back(i);
    }
  }
  for (int i = 0; i < state.size(); i++) {
    for (int j = 0; j < state.size(); j++) {
      int a = state[i], b = state[j];
      if ((a & b) == 0) {
        head[i].push_back(j);
      }
    }
  }
  f[0][0] = 1;
  for (int i = 1; i <= n + 1; i++) {
    for (int a = 0; a < state.size(); a++) {
      for (int b : head[a]) {
        if (g[i] & state[a]) continue;
        f[i][a] = (f[i][a] + f[i - 1][b]) % mod;
      }
    }
  }
  cout << f[n + 1][0] << endl;
  return 0;
}

炮兵阵地

292. 炮兵阵地

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int N = 11, M = 1 << 10;

int n, m;
int g[110];
vector<int> state;
int cnt[M];
int f[2][M][M];

bool check(int state) {
  for (int i = 0; i < m; i++) {
    if ((state >> i & 1) && ((state >> i + 1 & 1) || (state >> i + 2 & 1))) {
      return false;
    }
  }
  return true;
}

int count(int state) {
  int res = 0;
  for (int i = 0; i < m; i++) {
    res += state >> i & 1;
  }
  return res;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      char c;
      cin >> c;
      if (c == 'H') {
        g[i] += 1 << j;
      }
    }
  }

  for (int i = 0; i < 1 << m; i++) {
    if (check(i)) {
      state.push_back(i);
      cnt[i] = count(i);
    }
  }

  for (int i = 1; i <= n + 2; i++) {
    // 枚举第 i - 1 行状态
    for (int j = 0; j < state.size(); j++) {
      // 枚举第 i 行状态
      for (int k = 0; k < state.size(); k++) {
        // 枚举第 i - 2 行的状态
        for (int u = 0; u < state.size(); u++) {
          int a = state[j], b = state[k], c = state[u];
          // 三行之间两两不能有交集
          if ((a & b) | (b & c) | (a & c)) continue;
          // 大炮不能部署在山上
          if (g[i - 1] & a | g[i] & b) continue;
          f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
        }
      }
    }
  }
  cout << f[n + 2 & 1][0][0] << endl;
  return 0;
}

愤怒的小鸟

524. 愤怒的小鸟

#include <cmath>
#include <cstring>
#include <iostream>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 18, M = 1 << 18;
const double eps = 1e-6;

int n, m;
PDD q[N];
int path[N][N];
int f[M];

int cmp(double x, double y) {
  if (fabs(x - y) < eps) return 0;
  if (x < y) return -1;
  return 1;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
    memset(path, 0, sizeof path);
    for (int i = 0; i < n; i++) {
      path[i][i] = 1 << i;
      for (int j = 0; j < n; j++) {
        double x1 = q[i].x, y1 = q[i].y;
        double x2 = q[j].x, y2 = q[j].y;
        if (!cmp(x1, x2)) continue;
        double a = (y1 / x1 - y2 / x2) / (x1 - x2);
        double b = y1 / x1 - a * x1;
        if (cmp(a, 0) >= 0) continue;
        int state = 0;
        for (int k = 0; k < n; k++) {
          double x = q[k].x, y = q[k].y;
          if (!cmp(a * x * x + b * x, y)) state += 1 << k;
        }
        path[i][j] = state;
      }
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 0; i + 1 < 1 << n; i++) {
      int x = 0;
      for (int j = 0; j < n; j++) {
        if (!(i >> j & 1)) {
          x = j;
          break;
        }
      }
      for (int j = 0; j < n; j++) {
        f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
      }
    }
    cout << f[(1 << n) - 1] << endl;
  }
  return 0;
}