BZOJ 4145 [AMPPZ2014]The Prices (状压DP)

题意

你要购买商店，你到第i家商店的路费为，在第家商店购买第种物品的费用为，求最小总费用。

分析

• 很容易定义出状态，表示到第行，买的物品情况为的最小费用。按照往常的套路是转移时枚举子集，但那样的时间复杂度是太慢了，于是我们只需要现将上一次的所有复制到，然后在第行每一个数考虑取不取就行了。因为这一行可以不选，最后再与取一个最小值。时间复杂度

AC代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXM = 16;
const int MAXS = 65536;
int n, m, d[MAXN], cost[MAXN][MAXM], f[2][MAXS];
int main () {
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; ++i) {
    scanf("%d", &d[i]);
    for(int j = 0; j < m; ++j)
      scanf("%d", &cost[i][j]);
  }
  int now = 0;
  memset(f[now], 0x3f, sizeof f[now]); f[now][0] = 0;
  for(int i = 0; i < n; ++i) { now ^= 1;
    for(int state = 0; state < (1<<m); ++state)
      f[now][state] = f[now^1][state] + d[i];
    for(int j = 0; j < m; ++j)
      for(int state = 1; state < (1<<m); ++state) if((state>>j)&1)
        f[now][state] = min(f[now][state], f[now][state^(1<<j)] + cost[i][j]);
    for(int state = 0; state < (1<<m); ++state)
      f[now][state] = min(f[now][state], f[now^1][state]);
  }
  printf("%d\n", f[now][(1<<m)-1]);
}