http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202
上限金額が決まっていて、与えられた料理の金額を使ってそれぞれ0個以上用いて割り切れない最大の金額を求める。
「割り切れない」はすなわちその値が素数であることを示す。
「割り切れない」の意味が分かったので、取り敢えず「割り切れない」は横において、今度は問題の残りの部分の解釈に移る。
それぞれの料理を使う個数を決めて上限の金額を超えるまで全探索することはとてもできない。
添字が上限金額まで記憶可能なbool型の配列を用意して可能な合計金額をマーキングをしていこう。ある料理の値段を用いて新しくマークを付けるとき、既知のマークを始点としてある料理の金額分先にマーキングできる。初期条件としては合計金額が0円である自明なマーキングがある。
あとははじめの「割り切れない＝素数である」をと合わせてマーキングされた中で答えになりうる最大の金額を見つければ良い。
c[0] = 1;
for(int i=0; i<n; i++) {
cin >> b;
for(int j=b; j<MAX; j++) {
c[j] = c[j] | c[j-b];
}
}
int mx = -9999;
for(int i=0; i<=a; i++) {
if(c[i] && is_prime[i]) mx = max(mx, i);
}
if(mx == -9999) cout << "NA" << endl;
else cout << mx << endl;