题目描述
你要购买(m)种物品各一件，一共有(n)家商店，你到第(i)家商店的路费为(d[i])，在第家商店购买第(j)种物品的费用为(c[i][j])，求最小总费用。
输入格式
第一行包含两个正整数(n,m(1<=n<=100,1<=m<=16))，表示商店数和物品数。
接下来(n)行，每行第一个正整数(d[i](1<=d[i]<=1000000))表示到第(i)家商店的路费，接下来(m)个正整数，依次表示(c[i][j](1<=c[i][j]<=100000))。
输出格式
一个正整数，即最小总费用。
样例
样例输入
3 4
5 7 3 7 9
2 1 20 3 2
8 1 20 1 1
样例输出
16
题解
- 看数据，(m≤16)，明显小于20，首先想到状压dp 。
- 定义：(dp[i][j]) 表示前 (i) 个商店，买东西的状态为 (j) 时的最小花费。
- 首先枚举每个商家，然后加上路费。注意如果两次在同一条路上，需要减去重复的路费，路费只算一遍！！！
- 然后枚举第i个商家的m件商品，并进行状态转移条件判断：想买第k件商品，则前i-1个商家没有买k，所以j的二进制的第k为0
- 然后状态转移方程就很简单：
dp[i][j|(1<<k-1)]=min(dp[i][j|(1<<k-1)],dp[i][j]+a[i][k]); - 最后就不买第i个商家的物品和买第i个商家的物品的情况进行比较，选出最优解。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=(1<<16)+5;
int dp[105][maxn],a[105][20],d[105];
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&d[i]);
for(int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
}
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
int Max=1<<m;
for(int i=1;i<=n;++i){
for(int j=0;j<Max;++j)
dp[i][j]=dp[i-1][j]+d[i];
for(int k=1;k<=m;++k)
for(int j=0;j<Max;++j)
if(~j & (1<<k-1))
dp[i][j|(1<<k-1)]=min(dp[i][j|(1<<k-1)],dp[i][j]+a[i][k]);
for(int j=0;j<Max;++j)
dp[i][j]=min(dp[i][j],dp[i-1][j]);
}
printf("%d
",dp[n][Max-1]);
return 0;
}