the prices
题目大意
你要购买 (m) 种物品各一件，一共有 (n) 家商店，你到第 (i) 家商店的路费为 (d[i])，在第 (i) 家商店购买第 (j) 种物品的费用为 (c[i][j])，
求最小总费用。
Input
第一行包含两个正整数 (n,m) ( (1<=n<=100,1<=m<=16) )，表示商店数和物品数。
接下来 (n) 行，每行第一个正整数 (d[i](1<=d[i]<=1000000)) 表示到第 (i) 家商店的路费，接下来 (m) 个正整数，
依次表示 (c[i][j](1<=c[i][j]<=1000000)) 。
Output
一个正整数，即最小总费用。
样例
输入
3 4
5 7 3 7 9
2 1 20 3 2
8 1 20 1 1
输出
16
大致思路
首先要理解对题意！！！，是每个物品都要买一份，而不是买m件物品就行，不要理解错题意了（我猜只有我一开始想错了吧...），再看数据范围，怎么看都是状压dp啊，用二进制的每一位来表示该产品是否买过，一层一层的向下一个状态退，最后判断一下最大值即可，转移就好了，其实思路并不难想，代码也不难写，自己思考一下就能完成。(dp[i][j])表示的是前i个店在j状态的最小值。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn = (1 << 16) + 5;
int m,n,dp[105][maxn],a[105][20],d[105];
int Max;
void solve(){
scanf("%d%d",&n,&m);
Max = 1 << 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;
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]);
}
int main(){
solve();
return 0;
}
谢谢观看，喜欢的话点个关注～～