問題文 : カード解法 :dp(l, r) -> 区間(l, r)のカードを併合するために必要な最小コストとすると, l番目のカードが最も上に, r番目のカードが最も下になるのは明らかなのでdp(l, r) = min(dp(l, r), dp(l, i) + dp(i+1, r) + a[l] * b[i] * a[i+1] * b[r]) …

問題文 : サージェント・ライアン解法 : 最後に訪れる島を根とした木を作ると, 爆破する橋が必然的に決まる. ゆえに, 全ての島について最後の島としたときの爆破する時間を考え, その最小値を答えとする.コード : #include <cstdio> #include <cstring> #include <vector> #define INF</vector></cstring></cstdio>…

問題文 : 会津の埋蔵金解法 : f(ny, nx, l, r, oxygen) -> 現在場所(nx, ny)にいて, 深さny[m]のうちl ~ rまでの距離は移動済みで, oxygenだけ酸素をもっている, という状態をもった動的計画法を行う. 状態空間が5*10^4になるため, 楽にメモ化再帰ができる. …

問題文 : 人生ゲーム解法 : dp(i, j) -> 場所iにいてj円を持っている確率, とし動的計画法を行う. int型にキャストして表示することに注意.コード : #include <cstdio> #include <cstring> #include <algorithm> typedef struct { int dx; int money; } State; using namespace std; int </algorithm></cstring></cstdio>…

問題文 : 自転車ダイエット解法 : ケーキ屋の数が少ないので, 訪れたケーキ屋の集合および今いる頂点を持ったダイクストラを行う. "一度訪れたケーキ屋に再び訪れることができない"ということに注意.コード : #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #incl</algorithm></cstdlib></cstring></cstdio>…

問題文 : The Great Summer Contest解法 : 2つのペアをグループ化することが出来るので, 2つのペアをグループ化する. 4番目のタイプのコンテストは, 3つあると1 ~ 3番目のコンテストを1回ずつ開くのと同義になるので0回, 1回, 2回開く場合を考えて貪欲的にコ…

問題文 : 秋のイルミネーション解説 : 各四角形の交差判定ができれば, 各四角形を頂点とみて, 連結成分の個数を数える問題となる.連結成分の個数を求める方法は, union-find木を使う方法などもあるが, ここでは深さ優先探索で同等な事をしている.ここで, 四…

問題文 : ばらばら饅頭解法 : まず, 2個の饅頭で作る組み合わせが最適である(らしい) ので, 2個で作れる饅頭の個数を貪欲法で求める. (証明できなかった).その後は, ナップサック問題を解く要領でメモ化再帰を行う. このように, 配列に値を持たせて行うDPをm…

問題文 : AOJ 0247解法 : 基本的には深さ優先探索を行う. ただし, それだけでは時間制限に間に合わないので, 反復深化深さ優先探索(IDDFS)を行う. 具体的には, 下界uを決めて, uよりコストがかかることがわかればuを増やすという事を行う. 下界から決めてい…