P2145 [JSOI2007] 祖码

[JSOI2007] 祖码 - 洛谷https://www.luogu.com.cn/problem/P2145很经典的一道区间dp,区间dp的部分都挺好想的:

我们用数组f [ i ][ j ]表示消除区间[ i , j ]需要的竹子的个数.那么我们进行区间dp,从小区间合并到大区间,状态转移方程式(这里就是板子)就是

f [ i ][ j ]=min(f [ i ][ j ],f [ i ][ k ]+f [ k+1 ][ j ])

这里是先求出小区间的贡献值,在将小区间转换为大区间,求出大区间的贡献值.这就是常规部分的写法.但是还存在另外的情况.当区间两段的值相等arr[ i ]==arr[ j ],那么考虑我们是否可以把中间的部分消除后,两边是否能直接消除.如果这两个端点的相同颜色珠子数相加是大于3的,那么就可以不用发射弹珠,直接消灭,反之则是还需要射出一颗珠子.

现在就到了难点,我们如何判断这两端的珠子可以直接进行消去呢.如果判断这两个珠子两边是否同色,这样处理的话就超出了原有的需要处理的区间,是不可以去的.那么我们可以尝试把原来的珠子串进行压缩把他们压缩成一个个区间:

for(int i=1;i<=n;++i){cin>>arr[i];if(i!=1&&arr[i]==arr[i-1])b[tot]+