题目描述

Description

你要购买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

一个正整数，即最小总费用。

Sample Input

3 4
5 7 3 7 9
2 1 20 3 2
8 1 20 1 1

Sample Output

16

HINT

在第一家店买2号物品，在第二家店买剩下的物品。

题目分析

状压DP
每个商店之间互不影响 那么就先预处理 表示在所有商店里 买到集合s物品的最小花费
然后对于枚举物品的状态 对于每个状态枚举子集来更新自己
时间复杂度

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,a[111],g[1<<17],f[1<<17];
int read()
{
    int sum=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') sum=sum*10+(c-'0'),c=getchar();
    return sum;
}
int mi(int x,int y) { return x>y?y:x ; }
void dfs(int id,int sum,int s)
{
    g[s]=mi(g[s],sum);
    if(id>m) return ;
    dfs(id+1,sum,s),dfs(id+1,sum+a[id],s|(1<<(id-1)));
}
int main()
{
    n=read(),m=read();
    memset(g,0x3f,sizeof g),g[0]=0;
    for(register int x,i=1;i<=n;i++)
    {
        x=read();
        for(register int j=1;j<=m;j++) a[j]=read();
        dfs(1,x,0);
    }
    for(register int i=1;i<(1<<m);i++)
    {
        f[i]=0x3f3f3f3f;
        for(register int j=i;j;j=i&(j-1)) 
            f[i]=mi(f[i],g[j]+f[i^j]);
    }
    printf("%d",f[(1<<m)-1]);
}