yukicoder 1368 サイクルの中に眠る門松列

円環だが, この問題の場合考えるべきなのは数列の長さ+3までなので+3の部分を全探索することを考える. すると通常の数列の形になる.

$ dp_i := 今考えている数列の$ i番目まで見たときの評価値の総和の最大値とすると, 遷移は門松列かどうかを判定することで非常に簡単にすることができる(この問題の場合も門松列かどうかを判定する関数を用いると実装が楽になる).

計算量は$ O(T \sum_{i}N_i)となる.