Codeforces 279D (171D) The Minimum Number of Variables

Codeforces 動的計画法

問題

n項からなる数列aが与えられる。
m個の変数bに対して次のような操作をn回行う。

  • 最初、全ての変数は0
  • t回目の操作で、b[y] := b[i] + b[j]とbを更新する。このとき、b[i] + b[j] = a[t]でなくてはならない。


この操作が行える変数の数の最小値を求めよ。
変数がいくつあっても操作を行えないとき、-1を出力せよ。

制約条件

a[i]は全て互いに異なる。
a[i]≦10^9
n≦23

方針

i番目の操作まで行ったとき、変数のなかに残っているaの集合をbitとするときの、
変数の数の最小値をdp[i][bit]とする。
これを更新するようなDPをする。


状態数は2^nで、
それぞれに対してi番目の操作が行えるかを判定するのを上手くやるとn、
消す数を選ぶのにnかかるので、
全体でO(2^n n)の計算量がかかる。


判定を上手くやるのは、a[i]が互いに全て異なるということを使う。
a[i] = a[j] + a[k]となるi, j, kは、i, jを決めれば一通り以下に定まる。
したがって、jをn通り探すだけで、状態がvalidかどうか判定できる。

ソースコード

メモリを23*2^23じゃなくて2^23に節約してある。

int n, a[23], dp[1 << 23], p[23][23];

int main(){
	cin >> n;
	rep(i, n) cin >> a[i];
	rep(i, 1 << n) dp[i] = inf;
	dp[1] = 1;
	
	memset(p, -1, sizeof(p));
	rep(i, n) rep(j, n) rep(k, n) if(a[k] == a[i] + a[j]) p[k][i] = j;
	
	for(int i = 1; i < n; i++) rep(j, 1 << i) if((j & 1 << i - 1) && dp[j] < inf){
		bool ok = 0;
		rep(k, i) if(j & 1 << k){
			int t = p[i][k];
			if(t >= 0 && (j & 1 << t)){
				ok = 1;
				break;
			}
		}
		if(!ok) continue;
		dp[j ^ 1 << i] = min(dp[j ^ 1 << i], dp[j] + 1);
		rep(k, i) if(j & 1 << k) dp[j ^ 1 << i ^ 1 << k] = min(dp[j ^ 1 << i ^ 1 << k], dp[j]);
	}
	int ans = inf;
	rep(i, 1 << n) if(i & 1 << (n - 1)) ans = min(ans, dp[i]);
	cout << (ans == inf ? -1 : ans) << endl;
	
	return 0;
}