[文章目录]
Description
你要购买m种物品各一件，一共有n家商店，你到第i家商店的路费为di，在第i家商店购买第j种物品的费用为cij，求最小总费用。1<=n<=100,1<=m<=16
状压DP，枚举子集。
将物品状态压缩，求出每个状态在每个商店购买价钱的最小值，发现答案是由一些子状态的并集构成。对每个状态枚举子集即可。时间复杂度O(n*2^m+3^m)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define R register
using namespace std;
int w[(1<<16)+64],dp[(1<<16)+64];
inline int Min(int x,int y){return x<y?x:y;}
int main()
{
int n,m; scanf("%d%d",&n,&m);
memset(dp,0x3f,sizeof(int)*((1<<m)+10));
int now,lim=(1<<m); dp[0]=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&now);
for(int j=0;j!=m;++j) scanf("%d",w+(1<<j));
for(R int s=1;s!=lim;++s)
{
w[s]=w[s-(-s&s)]+w[-s&s];
dp[s]=Min(dp[s],w[s]+now);
}
}
R int s1,s2;
for(s1=1;s1!=lim;++s1)
for(s2=s1;s2;s2=s1&(s2-1))
dp[s1]=Min(dp[s1],dp[s2]+dp[s1^s2]);
printf("%d",dp[lim-1]);
return 0;
}