只可意會不可言傳的DP ... 附上官方題解 Tutorial D. Dima and Hares Let's look at the first hare: we chose them befoe second, or after. If it is chosen after the second, than the solution from the 2nd hare to the last doesn't depend on the first one, otherwise, we will receive the same but before the second hair will be obviously the feed hair. So, we have two dinamics: 1). d 0 i — answer for suffix as a separate task. 2). d 1 i — answer for suffix if the previous hair for this suffix is feed already. Movements: d 0 n = an d 1 n = bn d 0 i = max ( ai + d 1 i + 1, bi + d 0 i + 1) d 1 i = max ( bi + d 1 i + 1, ci + d 0 i + 1) // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A::::