AOJ_0202 At Boss's Expense

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202

以前問題を見たとき「あ、これ無理なやつだ」と思ったもの。
できるようになっていた。

解法
素数の金額が作れるかを調べるのに動的計画法を用いる。
↑この発想がむりだった。
k[i] := 品物iの金額
m[i] := 金額iを品物の組み合わせで作れるか(true|false)
漸化式は
m[i] := (m[i - k[j] ] のいずれかがtrueならばtrue)
となる

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

const int MAX_M = 1000001;
bool p[MAX_M];
bool m[MAX_M];
int  k[30];
int main(){
	fill(p, p + MAX_M, true);
	p[0] = p[1] = false;
	for(int i = 2; i < MAX_M; i++){
		if(p[i])
			for(int j = 2*i; j < MAX_M; j += i)
				p[j] = false;
	}
	int n, x;
	while(scanf("%d %d", &n, &x) && n){
		fill(m, m + MAX_M, false);
		for(int i = 0; i < n; i++)
			scanf("%d", &k[i]);
		m[0] = true;
		for(int i = 1; i <= x; i++){
			for(int j = 0; j < n; j++){
				if(i - k[j] >= 0 && m[i-k[j]]){
					m[i] = true;
					break;
				}
			}
		}
		bool f = false;
		for(int i = x; i >= 0; i--){
			if(p[i] && m[i]){
				f = true;
				printf("%d\n", i);
				break;
			}
		}
		if(!f)
			printf("NA\n");
	}
}