bzoj 4145 [AMPPZ2014]The Prices

bzoj 4145 [AMPPZ2014]The Prices

​​ Description 你要购买m种物品各一件，一共有n家商店，你到第i家商店的路费为d[i]，在第i家商店购买第j种物品的费用为c[i][j]， 求最小总费用。

Input 第一行包含两个正整数n,m(1<=n<=100,1<=m<=16)，表示商店数和物品数。 接下来n行，每行第一个正整数d​​​i​​​表示到第i家商店的路费，接下来m个正整数， 依次表示c[i]​​​j​​。

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号物品，在第二家店买剩下的物品。

Source 鸣谢Claris上传

设dp[i][s]表示前i个商店购买s状态商品的最小代价 转移的时候背包转移即可

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=110;int n,m,d[N],c[N][20],dp[N][1<<16];int main(){ freopen("bzoj4145.in","r",stdin); n=read();m=read();int S=1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。