The Prices

The Prices
タイトルの説明
あなたは(m)種類の物品を1件ずつ購入して、全部で(n)軒の商店があって、あなたは第(i)軒の商店までの旅費は(d[i])、第1軒の商店で第(j)種類の物品を購入する費用は(c[i][j])で、最小の総費用を求めます.
入力フォーマット
最初の行は、2つの正の整数(n,m(1<=n<=100,1<=m<=16))を含み、商店数と物品数を表す.
次の(n)行は、各行の最初の正の整数(d[i](1<=d[i]<=100000))が(i)店までの旅費を表し、次の(m)個の正の整数が、(c[i][j](1<=c[i][j]<=100000))の順に表される.
出力フォーマット
正の整数、すなわち最小総費用.
サンプル
サンプル入力

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

サンプル出力

16

問題解

(m≦16)、まず状圧dpを思い浮かべる.

定義:(dp[i][j])は前(i)の店を表し、買い物の状態が(j)のときの最小費用を表す.

は、依存リュックサックと類似しており、具体的にはコードを参照してください.

code

#include 
typedef long long LL;
const int maxn=(1<<16)+5;
int dp[105][maxn],a[105][20],d[105];
void Solve(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
		for(int j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	int Max=1<