请问这个思路是否正确?
查看原帖
请问这个思路是否正确?
361592
histcat楼主2024/10/21 23:22

设dpi,0,1,2,3(pairint, int类型)表示选到第i列,第i列

0:一个没选

1:选了第一行

2:选了第二行

3:都选了

能获得的最大价值和选了几个 一黑一白中的黑

对于列算完之后都记录一下看能不能成为最大值

dp_i,0 不能向下传递了,直接赋值0,0

dp_i,1可以从dp_i-1,1和dp_i-1,3转移来

dp i,2可以从dp i-1,2 和dp i-1,3转移来

dp i,3可以从dp i-1,1 dp i-1,2 dp i-1, 3转移来

转移的时候,如果是dp x, 1 或者是dp x, 2 且 对应的是一黑一白中的黑,那么dp储存的第二位+1

转移的时候dp的价值 为 dp的价值 - min(dp的第二位, m) * 2

谢谢!!

2024/10/21 23:22
加载中...