POJ

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

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