keidaroo’s diary

底辺系競プロer

ABC-4 D マーブルポイント

解法

DPですね、枝狩り全探索でもできますが、コードを書くのが面倒です。(枝狩りは10^6ぐらいではいけそう)

ポイント1

この状況、ありえなくね?って思ってもとりあえずDPにぶちこむ!!

→もし状況自体がありえなくても、それが最適解になる可能性もありえないのであればDPにぶちこめる!!
 

ポイント2

簡単なDPから考える!!

ミドリムシ君の練習を見ているとこれをしていて、難しいDPから簡単なDPに落とし込めるなあ、と

ポイント3

順序だっているものは省略できる!!

今回の場合は色で順序付けできます、それをつかって合計数で省略をしましょう