POJ-3688 : Cheat in the Game

問題概要

頑張って問題文を読むと、奇数個の部分和になりうるかつ偶数個の部分和になり得ない値の個数を求める問題だと解釈できないこともない。

解法

計算量O(N*M)だけど定数が軽いのと多分テストケースが弱いのとで普通にDPやって通る。

acceptされたコード

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N = int(1e4);
const int MAX_M = int(1e5);

int N, M;
int as[MAX_N];
bool reachable[2][MAX_M + 1];

bool init() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i) {
		scanf("%d", as + i);
	}
	return N > 0 && M > 0;
}

int solve() {
	memset(reachable, false, sizeof(reachable));
	reachable[0][0] = true;
	for (int i = 0; i < N; ++i) {
		for (int j = M; j >= as[i]; --j) {
			for (int p = 0; p < 2; ++p) {
				reachable[p][j] |= reachable[p^1][j-as[i]];
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= M; ++i) {
		if (reachable[1][i] && !reachable[0][i]) {
			++ans;
		}
	}
	return ans;
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}
	return 0;
}