给你两个序列a和b,你可以从中任意选取其中的数字,但是你不能取相邻的两个数字,问所取的数字的最大和.
但是写的DP题少啊.DP还是相当苦手.
需要多刷点题.不过最近没啥时间,要期末考了.等暑假吧.
我们可以用$dp[i][j][h]$来表示第i列到序列最右端的最大和,其中j代表第几行,h代表这一位取或者而不取.
那么我们便可以得到状态转移方程.
假如我第i位不取,那么无论是第1行,还是第2行,都是右边所有情况的最大值,因为我这一位不取,不会影响到后面的取舍,所以只需要取其中的最大值即可.
假如我第i位取,那么对第一行来说,我不能取第一行后面相邻的那个数,但是对第二行的取舍是没有影响的,所以取这三种情况的最大值并且加上该位上的值即可.
对于第二行来说是类似的,我不能取第二行后面相邻的那个数,但是对第一行的取舍是没有没有影响的,所以也是取这三种情况的最大值加上该位上的值即可.
但是需要注意,我们需要从右边开始倒序转移,因为重叠的子问题都是与右边的情况有关的.
最后的结果就是第一列中第一行取或不取,第二行取或不取四种情况中的最大值.
版权声明: 本博客所有文章除特别声明外,著作权归作者所有.转载请注明出处!