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

あなたはstackをひとつ持っている

探索して、物を拾ったり取り出したりしてなんらかの対応をつけます きちんと対応付けできるか?とか対応付けの個数の最大値は?みたいな問題があります
典型的な例が Stack Maze (AOJ2538)です
この場合探索する場所がDAGなので、区間DPが出来ます。何を持つかというとdp[v][u]="vからuまでで何個対応付けられるか"で、更新は(v-uが対応付いているか)+dp[next_v][prev_u]・・・ではなくて、v-u間のvと対応する各wに対し、1+dp[next_v][prev_w]+dp[next_w][u]とかにしなきゃダメです(前者だとaAbBとかで死ぬ)(前者をやった後にはしから取ってくようなDPとかをやっても、abBcCAとかで死ぬ)

当たり前なんだけど、区間を両側からずらしていこうみたいな発想があるとちょっと面倒なことを書きがちだし,a bBcCdD Aみたいなケースがあることを忘れそうなのでメモっておこう.

要はサボらないで全部の場所で区切りましょう(ただしvと対応づき,v-u間のとこだけ)という話