旧事重提

自己搭的博客好像炸了，最近没时间弄了。先用这个博客更新。

BZOJ1688：状压DP裸题，只要将普通背包DP的容量，变为01串即可。

核心DP转移片段：

// Author: 23forever
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
typedef long long LL;
const int MAXN = 200000;
using namespace std;

inline int read() {
  int x = 0, w = 1;
  char c = ‘ ‘;

  while (c < ‘0‘ || c > ‘9‘) {
    c = getchar();
    if (c == ‘-‘) w = -1;
  }
  while (c >= ‘0‘ && c <= ‘9‘) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }

  return x * w;
}
 
int n, d, k, dp[1 << 15], c[MAXN + 5];
 
void init() {
  n = read();
  d = read();
  k = read();
  for (int i = 1; i <= n; ++i) {
    int t = read();
    for (int j = 1; j <= t; ++j) {
      int x = read();
      c[i] |= (1 << (x - 1));
    }
  }
}
 
bitset<15> B;
 
int main() {
#ifdef forever23
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#endif
  init();
 
  int N = 1 << d;
  for (int i = 1; i <= n; ++i) {
    for (int cur_state = N - 1; ~cur_state; --cur_state) {
      int nxt_state = cur_state | c[i];
      dp[nxt_state] = max(dp[nxt_state], dp[cur_state] + 1);
    }
  } 
 
  int ans = 0;
  for (int s = 0; s < N; ++s) {
    B = s;
    if (B.count() <= k) ans = max(ans, dp[s]);
  }
  printf("%d\n", ans);
  return 0;
}

BZOJ1601：如果不能自己建水库，那么就是MST板题。我们将所有点都连向一个超级汇，表示在该点建造水库的代价。然后跑MST即可。

洛谷P：区间DP板题，可以转化成合并石子的问题，然后注意两个区间拼起来时的代价。

for (int l = 2; l <= m; ++l) {
    for (int i = 1; i <= m; ++i) {
      int j = i + l - 1;
      if (j > m) break;
    
      int v = l - 2 + sum[j] - sum[i - 1];
      for (int k = i; k < j; ++k) {
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + v);
      }
   }
}

BZOJ1621：暴力，emmm。

旧事重提

原文：https://www.cnblogs.com/23forever/p/10159434.html