【BZOJ 4145】[AMPPZ 2014]The Prices状圧dp

the prices
テーマの大意
あなたは(m)種類の物品を1件ずつ購入して、全部で(n)軒の商店があって、あなたは第(i)軒の商店までの旅費は(d[i])、第(i)軒の商店で第(j)種類の物品を購入する費用は(c[i][j])で、最小の総費用を求めます.
Input
最初の行は、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))を表す.
Output
正の整数、すなわち最小総費用.
サンプル
入力

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

しゅつりょく

16

大まかな考え方.
まずは問題の意味を理解する!!!m品ではなく、すべての品物を1部買わなければなりません.問題の意味をまちがえてはいけない(最初は思い違いだったのかな…)、データ範囲を見てみると、どう見ても形圧dpですね、その製品を買ったことがあるかどうかはバイナリの1人1人で表していますが、1階1階の次の状態に下がって、最後に最大値を判断すればいいので、移せばいいのですが、実は考え方は難しくなく、コードも書きにくくなく、自分で考えてみれば完成します.(dp[i][j])前のi店のj状態の最小値を表す.
コード実装

#include
using namespace std;
const int maxn = (1 << 16) + 5;
int m,n,dp[105][maxn],a[105][20],d[105];
int Max;
void solve(){
	scanf("%d%d",&n,&m);
	Max = 1 << 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;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < Max; j++){
			dp[i][j] = dp[i-1][j] + d[i];
		}
		for(int k = 1; k <= m; k++){
			for(int j = 0; j < Max; j++){
				if(~j & (1 << k-1)){
					dp[i][j | (1 << k-1)] = min(dp[i][j | (1<

见てくれてありがとう、好きなら注目してね～～