P2612 ZJOI2012 波浪

解法は挿入 dp で 1 から i を何個の連続した区間として持つかを考えれば$ \mathrm{O}(N^4)にはなる。ただ、小数ジャッジなのがかなり苦労した。long double でも桁が足りなかったので __float128 を使った。(この 2 個が精度が違うことを始めて知った。)

ただ、そうすると私の解法だと遷移が多くて TLE してしまったので制約を利用して$ Nが大きいときは long double、そうでないときは __float128 を使うことで AC を得た。どうしてこの手の問題を mod ジャッジで出さなかったのだろうと思ったが、2012 年の問題なのでまだ mod ジャッジがなかったのかもしれない。