首页 > 其他分享 >消木块

消木块

时间:2024-01-25 23:58:29浏览次数:21  
标签:状态 颜色 相同 前面 木块 消掉

假设我们按照常规的方程设置的方法,设\(f[i][j]\)表示消除区间\([i,j]\)所有木块的最大得分,我们考虑最后一段颜色相同的木块

这一段木块要么自己被单独消掉,要么与前面颜色相同的木块一起消掉

对于第一种情况,这个操作肯定可以在最开始做而不影响答案,所以有\(f[i][j]=f[i][k]+value\),其中\([k+1,j]\)的颜色相同

对于第二种情况,我们可以调整操作顺序,先消掉前面颜色相同的木块和最后这段颜色相同的木块中间的木块(注意这中间的木块也可能有颜色相同的木块,到时候枚举就可以了),然后让最后这段颜色相同的木块和前面颜色相同的木块拼在一起,考虑怎么消掉剩下的木块

然后到这个时候,你就会发现推不走了,因为没有一个状态能够表示剩下的木块了,所以要调整状态

可能我们会想到一个状态\(f[i][j][k]\)表示区间\([i,j]\),最后有\(k\)个木块颜色相同

但是这样做的问题就是仍然没有办法表示剩下的木块,注意\(f[i][p][t]\)(其中\(t\)表示最后这段颜色相同的木块和前面颜色相同的木块拼在一起的木块总数,\(p\)表示前面颜色相同的木块的最前面的木块的前面一个木块,即颜色不同的最后一个木块的位置)是不对的,因为这个状态就是错的,\([i,p]\)这个区间的末尾根本没有\(t\)个颜色相同的木块

但是我们可以发现,剩下的木块只是末尾多了一些相同的木块,所以我们可以想到如下状态表示

标签:状态,颜色,相同,前面,木块,消掉
From: https://www.cnblogs.com/dingxingdi/p/17988438

相关文章