AMPPZ2014 The Prices

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Fri Oct 19 23:09:31 CST 2018

In Category: NoCategory

Description：

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

$1\leqslant n\leqslant 100,1\leqslant m\leqslant 16$

Solution：

预处理一个 $minc[S]$ 表示在一家商店购买集合 $S$ 中全部物品的最小费用，然后状压 $DP$ 就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 110

#define MAXM 17

int f[1 << MAXM];

int d[MAXN];

int c[MAXN][MAXM];

int cost[MAXN][1 << MAXM];

int minc[1 << MAXM];

int lowbit(int x){return x & (-x);}

int bit[1 << MAXM];

int main()

{

	scanf("%d%d",&n,&m);

	int tot = (1 << m) - 1;

	for(int i = 1;i <= m;++i)bit[1 << (i - 1)] = i;

	memset(minc,0x3f,sizeof(minc));

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&d[i]);

		for(int j = 1;j <= m;++j)

		{

			scanf("%d",&c[i][j]);

		}

		for(int b = 1;b <= tot;++b)

		{

			cost[i][b] = cost[i][b ^ lowbit(b)] + c[i][bit[lowbit(b)]];

			minc[b] = min(minc[b],cost[i][b] + d[i]);

		}

	}

	memset(f,0x3f,sizeof(f));

	f[0] = 0;

	for(int s = 1;s <= tot;++s)

	{

		for(int i = s;i != 0;i = (i - 1) & s)

		{

			f[s] = min(f[s],f[s ^ i] + minc[i]);

		}

	}

	cout << f[tot] << endl;

	return 0;

}

In tag: DP-状压DP

wjh15101051