「AOJ0557 A First Grader」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*AOJ0557 A First Grader
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557]
参考サイト
**解説
+と-の2択を選びつつ様々な制限の元ansに一致する場合数を列挙します。
2択で処理を進めるので全探索するとO(2^n)です。取りあえず再帰で全探索コードを考えてみましょう。
数列中の今見ている項とそこまでの計算結果の2つの情報が必要です。例外処理を省略して書いてみます。
>||
int rec(int index, int sum) {
if(index == tail) return sum == ans;
return rec(index+1, sum + seq[index+1]) + rec(index+1, sum - seq[index+1]);
}
||<
同じ項を見ているときそこまでの計算結果も同じなら、その後の計算が無駄になります。計算結果を再利用しましょう。メモ化再帰です。
>||
int rec(int index, int sum) {
if(memo[index][sum] == -1) return memo[index][sum];
if(index == tail) return sum == ans;
return memo[index][sum] = rec(index+1, sum + seq[index+1]) + rec(index+1, sum - seq[index+1]);
}
||<
*AOJ0557 A First Grader
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557]
参考サイト
**解説
+と-の2択を選びつつ様々な制限の元ansに一致する場合数を列挙します。
2択で処理を進めるので全探索するとO(2^n)です。取りあえず再帰で全探索コードを考えてみましょう。
数列中の今見ている項とそこまでの計算結果の2つの情報が必要です。例外処理を省略して書いてみます。
>||
int rec(int index, int sum) {
if(index == tail) return sum == ans;
return rec(index+1, sum + seq[index+1]) + rec(index+1, sum - seq[index+1]);
}
||<
同じ項を見ているときそこまでの計算結果も同じなら、その後の計算が無駄になります。計算結果を再利用しましょう。メモ化再帰です。
>||
int rec(int index, int sum) {
if(memo[index][sum] == -1) return memo[index][sum];
if(index == tail) return sum == ans;
return memo[index][sum] = rec(index+1, sum + seq[index+1]) + rec(index+1, sum - seq[index+1]);
}
||<
これで無駄な計算が無くなり、O(ns) 100*21 = 2100通りとなりました。
DPしてみましょう。高校数学の漸化式のと同じように「初期条件」と「式そのもの」が必要です。
