状压DP/01背包
Orz Gromah
容易发现m的范围很小……只有16,那么就可以状压,用一个二进制数来表示买了的物品的集合。
一种简单直接的想法是:令$f[i][j]$表示前$i$个商店买了状态集合为$j$的商品的最小代价,那么我们转移的时候就需要枚举在第$i$个商店买了哪些商品吗,这样的话带上枚举子集,复杂度就会变成$O(n*3^m)$,并不是我们能够忍受的……
那么怎么搞呢?我们每次转移的时候,不再枚举子集,而是搞一个类似01背包的东西:(以下来自Gromah)
我们首先令$f[i][j]=f[i-1][j]+d[i]$,表示到达第$i$个商店。
然后枚举每个状态$j$,以及每个不在$j$里的物品$k$,令:$$f[i][j+\{k\}]=min(f[i][j+\{k\}],f[i][j]+cost[i][k])$$
这个过程就相当于是进行了一次01背包。
最后还要令$f[i][j]=min(f[i][j],f[i-1][j])$看看在商店$i$时的购买计划是否划算。
时间复杂度$O(nm2^m)$,空间复杂度$O(n2^m)$。
/**************************************************************
Problem: 4145
User: Tunix
Language: C++
Result: Accepted
Time:6948 ms
Memory:29440 kb
****************************************************************/ //BZOJ 4145
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=,M=<<,INF=0x3f3f3f3f;
/*******************template********************/ int n,m,f[N][M],d[N],c[N][];
int main(){
#ifndef ONLINE_JUDGE
freopen("4145.in","r",stdin);
freopen("4145.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n){
d[i]=getint();
rep(j,m) c[i][j]=getint();
}
rep(j,<<m) f[][j]=INF;
f[][]=;
F(i,,n){
rep(j,<<m) f[i][j]=f[i-][j]+d[i];
rep(j,<<m) rep(k,m){
int s=<<k;
if ((j&s)==) f[i][j^s]=min(f[i][j^s],f[i][j]+c[i][k]);
}
rep(j,<<m) f[i][j]=min(f[i][j],f[i-][j]);
}
printf("%d\n",f[n][(<<m)-]);
return ;
}
4145: [AMPPZ2014]The Prices
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 70 Solved: 47
[Submit][Status][Discuss]
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
5 7 3 7 9
2 1 20 3 2
8 1 20 1 1
Sample Output
16
HINT
在第一家店买2号物品,在第二家店买剩下的物品。