土下座しながら探索中

主に競技プログラミング

動的計画法

AOJ 1086 : Live Schedule

問題リンク:Live Schedule | Aizu Online Judge解法: 動的計画法dp[何日目か][負担][連続してライブをした日数] := 最大利益 とする遷移の状態としては、 ・何もしない ・その場所だけでライブ ・連続してライブ の3つがあるEが0の時はそこでライブを行え…

AOJ 0537 : Bingo

問題リンク:Bingo | Aizu Online Judge解法: 動的計画法を行う 問題の制約より、N*Nのマスを全て異なる数で総和がSになるような状態の数を求めれば良い亊がわかるコード: #define REP(i,s,n) for(int i=s;i

UVa 108 : Maximum Sum

問題リンク:Maximum Sum問題概要: N*Nの2次元配列が与えられる この中から作れる長方形のうちその要素の和が最大のものをみつけよ解法: よくあるDP memo[y][x] := memo[y-1][x] + memo[y][x-1] - memo[y+1][x+1] + array[y][x]という配列を用意する array…

UVa 103 : Stacking Boxes

問題リンク:Stacking Boxes問題概要: n個のk次元の箱がある 以下の条件を満たす時、箱aを箱bに入れることができる ・箱aの各辺の長さが箱bの対応する辺の長さ未満であるような順列が存在する (例: 5次元とする 箱 a : 5 1 3 7 6 箱 b : 4 2 7 8 6分かりに…

AOJ 2517 : Hotel

問題リンク : Hotel | Aizu Online Judge解法: 動的計画法を行う D日間にかかるホテルの費用の最小は各日にちでもっとも安いホテルを選んだときの費用の和だが、 移動回数の最小化や複数あったときに辞書順で最小のものを選びたいのでDPする配列は dp[何日…

AOJ 2106 : Enegy Transporter

問題リンク : Enegy Transporter | Aizu Online Judge問題概要: n個のノードが一直線上につながれている ノードはそれぞれ値を持つ 両端のノードと値が0のノード以外のノードは自分の値をマイナス1することで 右のノードの値に左のノードの値を加えること…

UVa 437 : The Tower of Babylon

問題リンク:The Tower of Babylon問題概要: x*y*zの長方形がn個(nは30以下)与えられる 以下の条件を満たすとき長方形を別の長方形に載せることができる 条件:長方形の上にのせる長方形の横と縦の長さは下の長方形の横と縦の長さ未満でないといけないこ…

AOJ 1222 : Telescope

問題リンク : Telescope | Aizu Online Judge問題概要: n個の点が円上に存在する その内m個を選んだ時にできる多角形の面積の最大値を求めよ解法: 動的計画法で解いた dp[始点となる点][最後に使った点][点を選んだ回数]:=その時の最大面積 とした for sp …

AOJ 1269 : Sum of Different Primes

問題リンク : Sum of Different Primes | Aizu Online Judge解法: 動的計画法を用いてあらかじめ結果をdp配列に入れておく dp[n][k] := nをk個の異なる素数でつくる時の数 dp[0][0] = 1 (0を0個の異なる素数で作る方法は一通りしかない)疑似コード: for i…

AOJ 1277 : Minimal Backgammon

問題リンク:Minimal Backgammon | Aizu Online Judge解法: 動的計画法で確率を計算した double dp[T][N] := ターンTにマスNにいる確率 とした 初期ではdp[0][0] = 1 とする疑似コード for t 0..T for n 0..N for i 1..6 dp[next_T][next_N] += dp[t][n]*(1…