tooh’s diary

半角全角、常体敬体が入り乱れるカオス

3/1 AtCoder(一個飛ばしのDP)

こんにちは。minori解散の一報を受け悲しみに暮れています。とーです。

悲しみのあまり金恋をぶっ通しでやり続けてしまいました。明日からはちゃんとした生活習慣に戻ります。

 

AtCoder

解くに至った問題(1問)

DPまとめコン:C

 

DPまとめコンC

解説がないので一応覚書として

DPを使うのは(題名からして)明らかなので、とりあえずどういうDPを作ればよいかなと考えたところ、i日目に活動aをやった時の幸福度の最大値は、i-1日目に活動b、活動cのいずれかをやった時の幸福度の最大値にi日目の活動aの幸福度を足したものになると考えれば

dp_a = [i番目には、i+1日目にaをやった時の幸福度の最大値]

というリストをdp_b,dp_cと作ってあげて(漸化式から簡単に作れる)、それぞれのN番目の要素を比較し、最大をとればよい

計算はO(N)だけかかるので、N<=10**5なら十分間に合う

atcoder.jp