ペンキ

一次元DPが大好きなので，ペンキ問題について書きます。

ペンキ問題は

おいおい，使いかけのペンキの缶を放っておいたら中のペンキが乾いてしまうよ。 | OJ

板がn枚あり，i番目の板の面積はs_iです。

ペンキの缶がたくさん(加算無限個)あり，1缶分のペンキで面積Sを塗ることができます。

板のうち何枚かを選んで全てペンキで塗り残しなく塗りたいのですが，一度ペンキの缶を開けたら，中身を全て使い切らなければいけません。

塗れる面積の最大値を求めて下さい。

という問題です。

この問題を見て全探索とか考えてる人はね，DPの威力を思い知れよ。

はい，動的計画法は，値が整数であることを利用して大きな表を作るのが特徴です。

今回は，大きさΣs+1の1次元配列を使います。塗れるかどうかにだけ着目するのでstd::bitsetでいいです。

i番目までから選んだものの和としてありうるものは，i - 1番目までから選んだものの和としてありうるものにi番目の値を足したものと足さなかったものなので，動的計画法でできます。計算量はΣis_i(だと思う)。全探索O(2^n)に比べれば，はい。(制約によるけど)

コードはこうなります：

#include <iostream>
#include <bitset>

#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)

int main(){
	int n, s[110], S, sum = 0, hoge = 0;
	std::bitset<1100000> able(1);
	std::cin >> n;
	REP(i, n){
		std::cin >> s[i];
		sum += s[i];
	}
	REP(i, n){
		RREP(j, hoge + 1) if(able[j]) able[j + s[i]] = 1;
		hoge += s[i];
	}
	std::cin >> S;
	for(int i = sum / S * S;; i -= S) if(able[i]){
		std::cout << i << std::endl;
		return 0;
	}
}

 いいですか，このやり方は強いですよ。std::bitset<1100000>をstd::array<int>(sum)に変えれば選び方を全て区別して，条件を満たすものが何通りあるかを調べることができます。似たような問題がatcoderで何度も出題されています。

強いので，普段使っていないという方は是非使って下さい。強くお勧めします。

ではまた。