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