問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2118数字が書いてあるグリッドが与えられる。 この数字の中から、4近傍に隣接しているもの同士をとらないように選んだとき選んだ数字の和を最大化せよ。 前の一行を覚えておくdp。 #include<iostream></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2488 区間dp。monge性を使わなくても通ってしまった。 dp[i][j]:=i~j番目までの点で木を作るときの最小コスト #include<vector> #include<iostream> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cctype> </cctype></string></queue></set></map></algorithm></iostream></vector>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070 dp[使った数字][和]:=場合の数 #include<iostream> #include<vector> #include<algorithm> #include<cassert> #define all(c) (c).begin(),(c).end() using namespace std; int count(int bits){ bits = (bits & 0x55555555)</cassert></algorithm></vector></iostream>…

問題文 http://uva.onlinejudge.org/external/110/11069.html1~nまでの頂点が一直線につながっている。このグラフから、どの頂点も隣り合っていない物の中で、これ以上頂点を追加できないものの数を数えよ。 dp[頂点]:=場合の数 とすると、頂点が2つ前のもの…

問題文 https://icpcarchive.ecs.baylor.edu/external/57/5790.pdf図のようにコストがついた玉がいくつか与えられる。ある玉を取り除くとそのコスト分だけ得点がもらえる。その玉の上に玉が無ければ取り除くことができる。得点を最大化せよ。 与えられる玉を…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=132014個以下の文字列が与えられる。これらの文字列を全てつなぎ合わせたときの文字列の長さの最小値を求めよ。 ビットDPした。 dp[ 最後に使った文字 ][ 今まで使った文字の集合 ]:=長さ…

典型DPコンテストB問題。 http://tdpc.contest.atcoder.jp/tasks/tdpc_game 自分は自分の得点を最大化する。 相手は相手の得点を最大化する→相手は自分の得点を最小化する と言い換えることができる。 #include<iostream> #include<vector> #include<algorithm> #define INF (1<<29) using</algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4201.pdfバルブを光らせるパターンが与えられるので、クエリで与えられるとおりにバルブを光らせるまでの最短手数を求めよ。 ビットDP。 dp[パターンのid][バルブの状態]:=最短手数 とすると、DAGの…

問題文 http://poj.org/problem?id=1159与えられた文字列を、文字を挿入する操作のみを行って回文にする。挿入する文字の最小個数を求めよ。 ↓と同じ。メモ化再帰。int型を使うとMLEする。 http://d.hatena.ne.jp/TobiasGSmollett/20130702/1372785990 #incl…

問題文 http://poj.org/problem?id=1157訳 http://wikiwiki.jp/pku/?1157%20LITTLE%20SHOP%20OF%20FLOWERS メモ化再帰した。 #include<iostream> #include<algorithm> #define INF (1<<29) using namespace std; int h,w,v[102][102],memo[102][102]; int rec(int a,int b){ if(a=</algorithm></iostream>…

問題文 http://livearchive.onlinejudge.org/external/40/4058.pdf縦3横nの長方形が、与えられた回転できないブロックで作る方法がいくつあるか求めよ。 f[ n ]:=横nの長方形の場合の数 とする。 g1[n],g2[n],g3[n],g4[n]についてはそれぞれ以下のような図形…

問題文 http://poj.org/problem?id=3254グリッドが与えられる。マスの数が1であるようなもののうちで、それぞれ4近傍に隣接しないような選び方がいくつあるか求めよ。 1行を覚えておくDP。 dp[ マスの番号 ][ 直前の1行の状態 ] := 場合の数 #include<iostream> #inclu</iostream>…

問題文 http://poj.org/problem?id=2441n頭の牛がいて、m棟の小屋がある。牛にはそれぞれ入れる小屋が決まっていて、全部の牛を小屋に入れるような入れ方が何通りあるかを求めよ。 ビットDPした。 dp[ 牛の番号 ][ どの小屋を使ったか ] := 場合の数配列がと…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4212.pdfn*mのグリッドが与えられる。マスの数字はそのマスにあるキャンディーの個数だ。このグリッドのあるマスからそのマスにあるキャンディーを全てとるとき、図のようにそのマスの左右のマスと上…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 Monge DP。 週刊spaghetti_sourceさんにわかりやすい説明があったので参考にしながら解いた。 http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915dp[ 左端 ][ 右端 ] := その…

問題文 http://poj.org/problem?id=1967 宝の位置とその宝を取れる制限時間が与えられる。任意の位置からスタートして、宝を全て拾うときの最短時間を求めよ。 区間DP。 l[訪れた区間の左端][右端]:=訪れた区間の左端を終端とする最短時間 r[訪れた区間の左…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1262無限にエネルギーのある車でレースをする。距離0の地点からスタートし、途中n個のチェックポイントがある。チェックポイントではタイヤの交換ができる。タイヤの交換にはb秒かかる。タ…

問題文 http://uva.onlinejudge.org/external/113/11310.html o oo oの二つで縦2,幅nのブロックを作るパターン数を求めよ。 ↓類題。 http://d.hatena.ne.jp/TobiasGSmollett/20130618/1371579981 ooooooooo ooooooooo のように長さnのパターン数をf[ n ], oo…

文字列aとbの編集距離を求めるプログラムを書いた。 wikipediaの擬似コード↓を参考にした。 http://en.wikipedia.org/wiki/Levenshtein_distance文字の挿入や削除、置換によって一つの文字列を別の文字列に変形するのに必要な手順の最小回数を編集距離という…

問題文 http://uva.onlinejudge.org/external/106/10625.html(1文字)->(文字列) のように変換表が与えられる。 さらに、 (文字列) (1文字 x) (数字 n) のようにクエリが与えられるので、文字列を変換表に従ってn回変換した時、文字列中に現れる文字xの個数を…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1175&lang=jp ビットDPで解いた。 dp[ 残っている円盤 ] := その状態がありえるかどうかcheckは円盤同士が重なっているかを判定する関数。 i countは立っているビットの数を数える関数。 #…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120 ビットDPで解いた。 dp[ すでに置いたケーキ ][ ケーキの番号 ] := 横幅countは立っているビットの数を数える関数。 #include<iostream> #include<vector> #include<string> #include<cstdio> #include<cmath> #include<algorithm> #include<climits></climits></algorithm></cmath></cstdio></string></vector></iostream>…

問題文 http://uva.onlinejudge.org/external/107/10739.html文字列が与えられる。ある１文字を追加、削除、置換することができる。 この３つの操作を繰り返すことで回文を作りたい。 操作を繰り返す回数の最小回数を求めよ。 l r l r 追加 e b c d a e b c …

問題文 http://uva.onlinejudge.org/external/104/10404.htmlStanとOllieが石をnum[ i ]個ずつ取っていって最後のひとつを取ったほうが勝ち。どちらが勝つか判定せよ。 蟻本4-2章そのまま。解きなおした。 dp[ 残っている石の個数 ] := 勝敗dp[ 0 ] = 負け d…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1176&lang=jp メモ化再帰した。再帰関数の引数は左上の位置と右下の位置+1。 配列uは累積和を計算しておいた。 #include<iostream> #include<algorithm> #define f first #define s second #define INF (1<<29) </algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1126 上と左の数の後ろにのみ現在の数をつけることができる。最大の数字を出力せよ。 動的計画法。 dp[ y ][ x ]:=最大の数字の文字列 grid[ y ][ x ]:=入力 とすると dp[y][x]=max( dp[ y…

問題文 http://uva.onlinejudge.org/external/109/10911.htmln*2個の点の座標が与えられる。これらの点をペアにしたときの2点間の距離の和の最小値を求めよ。 ビットDPした。 dp[使った点の集合]:=距離の和の最小値 #include<iostream> #include<vector> #include<algorithm> #include<string> #in</string></algorithm></vector></iostream>…

問題文 http://uva.onlinejudge.org/external/109/10918.html2×1のタイルを使って3×nの長方形を作るときの作り方が何通りあるかを求めよ。 f[横の長さn]:=3×nの長方形の作り方の総和 g[横の長さn]:=3×nの長方形から隅を一つ消した形の作り方の総和 ....... A…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020&lang=jp 確率DP。 dp[使ったバッテリーの量][Y座標][X座標]:=確率dp[k+1][y+dy[ i ] ][x+dx[ i ] ]+=dp[k][y][x]/4もしその方向に動けない場合はdp[k+1][y][x]+=dp[k][y][x]/4 #inclu…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1167&lang=jp 典型的な動的計画法。 i * ( i + 1 ) * ( i + 2 ) / 6 円玉で n 円作るときの最小枚数。dp1[作る正整数]:=正四面体の最小個数 dp2→奇数しか使えないとき #include<iostream> #include<algorithm> #</algorithm></iostream>…