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"); } }