题目大意
过于简单,不在累赘,请自行理解
思路
考虑 dp。
设 dpi,jdp_{i,j}dpi,j 为第 iii 天选择活动 jjj 时的最大总愉悦值,其中 j∈{0,1,2}j \in \{0 , 1 ,2\}j∈{0,1,2} 分别对应活动 A,B,CA,B,CA,B,C。同时由于不能连续两次选择一样的活动,即 dpi−1,jdp_{i - 1,j}dpi−1,j 与 dpi,jdp_{i , j}dpi,j 无关联。
稍加思考后,我们得出,对于i≥2i \ge 2i≥2时的转移方程:
dpi,0=max(dpi−1,1+Bi,dpi−1,2+Ci)dp_{i , 0} = \max(dp_{i-1,1} + B_i , dp_{i - 1 , 2} + C_i) dpi,0 =max(dpi−1,1 +Bi ,dpi−1,2 +Ci )
dpi,1=max(dpi−1,0+Ai,dpi−1,2+Ci)dp_{i , 1} = \max(dp_{i-1,0} + A_i , dp_{i - 1 , 2} + C_i) dpi,1 =max(dpi−1,0 +Ai ,dpi−1,2 +Ci )
dpi,2=max(dpi−1,0+Ai,dpi−1,1+Bi)dp_{i , 2} = \max(dp_{i-1,0} + A_i , dp_{i - 1 , 1} + B_i) dpi,2 =max(dpi−1,0 +Ai ,dpi−1,1 +Bi )
初始状态:
dp1,0=A1,dp1,1=B1,dp3,0=C1dp_{1 , 0} = A_1 ,dp_{1 , 1} = B_1,dp_{3, 0} = C_1 dp1,0 =A1 ,dp1,1 =B1 ,dp3,0 =C1
最后输出 333 中情况里的最大值即可(即最后一天分别选择活动 A,B,C)
AC代码
当然,可以进行滚动数组优化/使用递推以做到更好性能。但是会导致代码可读性降低,因此不给出代码。(实际是上不想写)