「AOJ0202 At Boss's Expense」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*AOJ0202 At Boss's Expense
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202]
**解説
上限金額が決まっていて、与えられた料理の金額を使ってそれぞれ0個以上用いて割り切れない最大の金額を求める。
「割り切れない」はすなわちその値が素数であることを示す。
「割り切れない」の意味が分かったので、取り敢えず「割り切れない」は横において問題の残りの部分を解釈してみよう。
それぞれの料理をa[i]個使うとして全探索することは料理の個数の上限がないのでとてもできない。
添字が合計金額まで記憶可能なbool型の配列を持ってにマーキングをしていこう。ある料理の値段を用いて新しくマークを付けるとき、既知のマークを始点としてある料理の金額分先にマーキングできる。初期条件として、0円は支払い可能であることを示す自明なマーキングが必要。これでbool型の漸化式が作れる。２重ループすればすべての金額の組み合わせにおけるマーキングが完了する。
あとははじめの「割り切れない＝素数である」を用いて解けば良い。
>||
for(int i=0; i<n; i++) {
cin >> b;
for(int j=b; j<=sum; j++) {
c[j] = c[j] | c[j-b];
}
}
||<
*AOJ0202 At Boss's Expense
**サイト
[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;
||<
