『动态规划·奇葩状态设计』消木块 Blocks

编程入门行业动态更新时间:2024-10-09 22:23:12

『动态规划·奇葩状态设计』消<a href=https://www.elefans.com/category/jswz/34/1284243.html style= 木块 Blocks"/>

显然是一个区间DP，最直观的思路就是设置状态 f [ l ] [ r ] f[l][r] f[l][r]为区间 [ l , r ] [l,r] [l,r]的最高得分。

但是对于中间消除以后再消边上操作会十分困难，我们这里采用一种费用提前计算的方法：

我们设 f [ l ] [ r ] [ k ] f[l][r][k] f[l][r][k]表示在区间 [ l , r ] [l,r] [l,r]消完以后，还要消在 r r r右边颜色和 r r r一样的 k k k个的方案数。

我们可以用这幅图来诠释这个状态转移方程。

第一种情况，若 r r r不能与 r − 1 r-1 r−

更多推荐

『动态规划·奇葩状态设计』消木块 Blocks

本文发布于:2024-02-13 23:54:50，感谢您对本站的认可！

木块奇葩状态动态 Blocks

评论列表（有 0 条评论）