区间DP

/ 0评 / 0

这段时间做了区间DP在此总结下

1.POJ 1651 Multiplication Puzzle

题意描述:

给出序列$a$,求出最小得分—— 取出的数左边的数右边的数 (不能取两边),实质为矩阵链乘变形,设$dp[i][j]$为取光$(i,j)$之间的元素所得的最小值, $k$为区间$(i,j)$最后取出的元素,这样转移就可以维持状态方程的一致性
$cmin(dp[i][j], DP(l,k)+DP(k,r)+a[k] \cdot a[l] \cdot a[r])$,
因为如果$k$为第一次取出的元素的话不好确定$k$左右的临近元素

写法区间DP入门题之记忆化写法

之迭代写法

2. HDU 5115 Dire Wolf

题目描述

给出$n$只狼, 每只狼有基础攻击和给相邻的带去增益攻击,问以一个怎样的消灭顺序能得到最少的伤害

解法

区间$DP$,设$dp[i][j]$为消灭区间$(i,j)$所有狼收到的最小伤害,那么当$i=j+1$时$dp[i][j]=0$

设$k$为区间$(i,j)$最后取出的元素,递归处理$[l,r]$区间的每一个元素$cmin(dp[i][j],DP(l,k)+DP(k,r)+a[k]+b[l]+b[r])$

代码:

3. HDU 4570Multi-bit Trie

题目描述:

$LPM$最长前缀匹配从转发信息库$(FIB)$中找出匹配输入数据包的目的地址输出相应的$Next \ Hop \ information$
变态题意:一个长度为$n$的数列将其分成若干段每一段长度要求小于$20$,$\sum(a_i\times (2^{b_i}))$ $b_i$是每一段的长度,$a_i$是每一段的首元素的值。样例$n=7,A={1,2,4,4,5,4,3}$的最佳分法是$1 \ 2 \ 4 \ | \ 4 \ 5\ |\ 4\ |\ 3$ ,这样的$\sum=1\times 8+4\times 4+4\times 2+3\times 2=38$

解法:区间$DP$ ,序列的长度不超过64,每层长度不大于20

代码:

4. CF 149 D Coloring Brackets

题意:给出括号序列染色要求
1.括号要么不被染色要么染成红或蓝色
2.相邻的括号要染色保持不同
3.相匹配的括号有且只有一个被染色

$dp[l][r][x][y]$为$[l,r]$表示给$[l,r]$染色且端点$l$染$x$色,右端点$r$染$y$色 <0,1,2>分别为<plain, red, blue>
if <l,r> is matched ,那么由去掉这个嵌套的$dp[l+1][r-1][x][y]$转移出$dp[l][r][x][y]$枚举$l+1,r-1$的颜色

if <l,r> isn't matched,那么可以找到和l匹配的括号位置mid,求出$dp[l][mid][][]$和$dp[mid+1][r][][]$
枚举$l,mid,mid+1,r$这四个位置的颜色$i,j,x,y$ 有转移方程
if(j*x==0||j!=x) $dp[l][r][i][y]=(dp[l][r][i][y] + dp[l][mid][i][j] \times dp[mid+1][r][x][y]%mod)%mod$;

代码:

5. UVA 10003 Cutting Sticks

题目描述:
给出长度为$N$的木条,要在$i-th$点位置切割,每次切割的代价是当前切割块的木条的长度。给出要切割的点问最小的花费。

解法:

区间$DP$,对于区间的划分顺序影响总结果用区间$DP$,带上代价划分

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注