The values you can make [Codeforces 359 : Div1 C, Div2 E]

問題

http://codeforces.com/contest/687/problem/C

n要素の数の集合ciが与えられ、そこから和がkとなるように部分集合をとる。
その部分集合から、更に、部分集合を作ってその和をとると、作ることができる数はどのようになるか。
（日本語が下手）

1 <= n,k <= 500
1 <= ci <= 500

帰納的考察（Editorial見た）

1. ぱっと見て、ナップサック問題っぽい -> DPかな？

普通のナップサック問題でのDPでは、
DP[何個目まで使って][あるパラメタの和がいくつで] = 何かの最大量 or 到達可能性
みたいなのが一般的な感じかなと思います

2. DPを作るとすると、DP[何個目まで使って]までは決まりそうです
これだと、O(n)なので、計算量が余る

3. 他に要素となりそうなのは、和なので、これを1つ使ってみると、DP[何個目まで使って][その集合の和がいくつで]
これだと、O(nk)なので、計算量などが多いDPであれば、このDPを使う場面もあります。

―――― 壁 ――――

4. もう一つ和を使ってみる DP[何個目まで使って][その集合の和がいくつで][その集合の部分集合で作れる数がいくつで] = 到達可能性
これだと、O(nk^2)なので、計算量が10^8ほどです。
ダメそうに見えますが、DPの更新計算は大抵あまり、重くないので普通に通ったりします。
（bitsetあたりを使うとより高速化できそうですが、ややこしくなるのでやってないです。というか使ったこと無い）

5. このDPを更新するように考えてみると、更新式はさほど難しくないです(iiは既に使われているkの代わりです)
DP[i][j][ii]がtrueならば、DP[i+1][j][ii], DP[i+1][j+ci][ii+ci], DP[i+1][j+ci][ii]もtrue

実装

http://codeforces.com/contest/687/submission/18834033

int n, k;
bool dp[501][501][501];
//-----------------------------------------------------------------
int main() {
	scanf("%d %d", &n, &k);

	rep(i, 0, n) rep(j, 0, k) rep(ii, 0, k) dp[i][j][ii] = false;
	dp[0][0][0] = true;

	rep(i, 0, n) {
		int c; scanf("%d", &c);
		rep(j, 0, k + 1) rep(ii, 0, k + 1) if(dp[i][j][ii]){
			dp[i + 1][j][ii] = true;
			if (j + c <= k) {
				dp[i + 1][j + c][ii] = true;
				dp[i + 1][j + c][ii + c] = true;
			}
		}
	}

	vector<int> ans;
	rep(ii, 0, k + 1) if (dp[n][k][ii]) ans.push_back(ii);
	
	printf("%d\n", ans.size());
	for (int i : ans) printf("%d ", i);
	printf("\n");
}