読者です 読者をやめる 読者になる 読者になる

olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

IOI列車で行こう(13本選2)

N両の電車とM量の電車が与えられる。それぞれはI列車とO列車のみで構成される。

順にどちらかの先頭の車両を取っていき、IOIOIOIOIのようにIとOか交互に並び、且つIが端にあるように並べたとき、最長の長さを求める問題。

なお、電車はあまらせてもよいし、ぞれぞれ先頭から好きなだけポイしてもよい

dp[Sのi両目][Tのj両目まで使い[長さが偶数or奇数]の時の長さの最大値

をもってDPを回す。

計算量は(N+M)

難易度は6程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2327262#1