連結成分毎に独立で考えられる 連結集合毎の選び方の個数の積が答え それぞれの連結成分で連続する2数の内どちらかは選ぶ必要があるので最初を選んだかどうかでDPをする 両方とも$ dp_i = dp_{i+1}+dp_{i-2}だが$ dp_0が違う それぞれの連結集合毎にそのサイズの線型時間で解けるので$ \mathcal{O}(N) 問題: https://atcod…