動的計画法

AtCoder Beginner Contest 041 D - 徒競走

問題概要 リンク 略 解法 コメント #define MAX_N 16 int N,M; ll dp[1 << MAX_N]; bool edge[MAX_N][MAX_N]; int main(){ ios::sync_with_stdio(false); cin >> N >> M; REP(i, M) { int x, y; cin >> x >> y;x--;y--; edge[x][y] = true; } // dp[mask]:=m…

POJ 3280 Cheapest Palindrome

POJは制約が多すぎる (unordered_mapが使えなかった) 問題概要 リンク N種類の文字で構成された長さMの文字列Sが与えられる この文字列にいくつかの文字を追加、あるいは削除して回文にする i番目の文字を追加するには、a_iのコスト、削除するにはb_iのコス…

POJ 2229 Sumsets

蟻本章末問題 問題概要 リンク ある数字Nが与えられる Nを2の累乗の数の和で表す 例えば4なら 4 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 そのような組み合わせは何通りか 解法 dp[i] := N=iの時の組み合わせの数 dp[i] = dp[i/2] + dp[i-1] then i mod 2=0 dp[i] = d…

POJ 3176 Cow Bowling

蟻本章末問題 問題概要 リンク ボーリングのピンが並んでる 一番前のピンを倒す その後ろのピンのうち左右どちらかのピンを倒すことができる さらに、その後ろのピンのうち左右どちらかのピンを倒すことができる 以上の作業を繰り返し一番後ろのピンまで倒す…

AtCoder Regular Contest B - せんべい

問題概要 リンク 1 ~ Nまでの数字が書かれたせんべいがランダムな順番で与えられる シカは1枚目から順にせんべいを食べるか、食べないか選ぶ シカは全部でK枚のせんべいを食べられる シカはn枚目のせんべいを見ている時, 1 ~ n枚目のせんべいの大小関係がわ…