Description
BPM想要购买m种物品，每种物品只用购买一件。现在一共有n家商店，但走到第i家商店的路费为d[i]，而在第i家商店购买第j种物品的花费为c[i,j]。问你最少需要花费多少钱。
Input
第一行包含两个正整数n,m，表示商店数和物品数。
接下来n行，每行先是一个正整数d[i]，表示到第i家商店的路费。接下来m个正整数，依次表示c[i,j]。
Output
一行一个整数，表示最小花费。
Hint
对于前30%的数据，1<=n,m<=7
对于前100%的数据，1<=n<=100,1<=m<=16,d[i],c[i,j]<=1000000
Source
BY BPM
Solution
数据中m极小，考虑状压dp
设f[i][j]为前i物品取状态为j的最小花费
可以发现每家商店最多进去一次，即d[i]最多只需要计算一次，那么每次单独拎出来+d[i]即可
Code
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
#include <algorithm>
#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define erg(i, st) for (int i = ls[st]; i; i = e[i].next)
#define fill(x, t) memset(x, t, sizeof(x))
#define max(x, y) (x)>(y)?(x):(y)
#define min(x, y) (x)<(y)?(x):(y)
#define ll long long
#define db double
#define INF 0x3f3f3f3f
#define N 101
#define M 17
#define L 1<<16|1
int f[2][L], c[N][M], d[N];
int main(void){
int n, m;
scanf("%d%d",&n,&m);
rep(i, 1, n){
scanf("%d",&d[i]);
rep(j, 1, m){
scanf("%d",&c[i][j]);
}
}
fill(f, 31);
f[0&1][0] = 0;
int lim = (1 << m) - 1;
rep(i, 1, n){
rep(j, 0, (1 << m) - 1){
f[i&1][j] = f[(i - 1)&1][j] + d[i];
}
rep(k, 1, m){
rep(j, 0, lim){
if (~j&(1<<k-1))
f[i&1][j|(1<<k-1)] = min(f[i&1][j|(1<<k-1)], f[i&1][j] + c[i][k]);
}
}
rep(j, 0, lim){
f[i&1][j] = min(f[i&1][j], f[(i - 1)&1][j]);
}
}
printf("%d\n", f[n&1][lim]);
return 0;
}