JOI2018ho-C Dango Maker 裏解法
はじめに
これはクソ解法です。
本番でこんなの書いてたら春合宿に落ちちゃうので、ちゃんとした解き方をしましょう。
考察
まず、図を書いてみると、どれか1つで団子を作れる場合、斜め方向に連結していくことが分かります。
という感じ。
依存関係を考えるとこの斜めごとに独立に考えられるので、UnionFindで集合にして管理をすることにします。（←ここから狂い始める
さて、こうして斜めごとの集合に分けられたものは、さらに2種類に分けることができます。
この画像の黄色と、青色のところの2種類です。緑はどちらにも属しています。
上の方から使う向きを決めていった時を考えます。
Gが真ん中にある青の部分は、全部縦にも全部横にもできるので、別で考えることにします。
そうすれば、残りで考える必要があるのは沢山の黄色です。
縦を使えば横が使えなくなり、横を使えば縦が使えなくなるので、縦と横のどっちか多い方を使えばいいと思うかもしれませんが、黄色が大量にあることを考えると、上の方と下の方で使うべき目がばらばらになるかもしれません。
これをDPで解きます。
dp[i][j]=i番目の連結成分を右上から見ていき、最後に使ったRGWがjの向きだった時の最大値
dpの遷移式がわりあい複雑なので注意する必要があります。
実装方針
右上から全部DFSとかしてもできるんでしょうが、辛すぎて死んじゃうので、UFで連結成分ごとに分けて、青を全部識別した後、右上から順に見つかった黄色から全部辿っていき、DPを更新していくのが楽です。（楽ではない）
実装
かなり大変です。
最後に
誰も読まないと思っているのでかなり雑です。
もしこれを理解したいという奇特な人がいたなら、
からTwitterを特定して、DMをください。
