こんにちは。minori解散の一報を受け悲しみに暮れています。とーです。
悲しみのあまり金恋をぶっ通しでやり続けてしまいました。明日からはちゃんとした生活習慣に戻ります。
解くに至った問題(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なら十分間に合う