区间dp复习笔记
区间dp
例题 石子合并
dp[l][r] 表示将 [l,r] 合并为一堆的最小代价
对于所有 l\le k < r
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+\sum_{i=l}^ ra[i])
对于每个 dp 我们可以枚举区间长度 len,l,r,k
初始化时 dp[l][r]=\begin{cases}0&l=r\\ 0x3f3f3f3f & l \ne r \end{cases}
具体代码
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int l=1,r=l+len-1;r<=n;l++,r++){
for(int k=l;k<r;k++){
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
}
}
}
环形dp
对于环形dp问题 我们可以化环为线
即将 a[i] 数组复制一份 使 a[i+n]=a[i]
之后的操作与区间 dp 相似
具体代码
for(int i=1;i<=n;i++){
cin>>a[i];
a[n+i]=a[i];
}
for(int i=1;i<=n*2;i++){
sum[i]=sum[i-1]+a[i];
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int l=1,r=l+len-1;r<=2*n;l++,r++){
for(int k=l;k<r;k++){
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
}
}
}
注意在最后输出时应查找 dp[1 \sim n][n\sim2*n-1]
for(int i=1;i<=n;i++){
ans=min(ans,dp[i][i+n-1]);
}
经典例题 能量项链 <7187> 
本题是一道很经典的环形 dp 问题 除状态转移方程外与前题相同
对于每个 dp[i][i] 的初始值为0 因为只有一颗珠子时无法释放能量
举个例子
(m,n)=(2,3)(3,5)(5,10)(10,2)
-
合并 (2,3) 和 (3,5) 时 l=1,r=2,k=1
dp[l][r]=30
此时变为了 (2,5)(5,10)(10,2) -
同理合并 (5,10)(10,2) 此时 l=3,r=4,k=3
dp[l][r]=100
此时变为了 (2,5)(5,2) -
最后合并 (2,5) 和 (5,2) 此时 l=1,r=4,k=2
dp[l][r]=dp[l][k]+dp[k+1][r]+2*5*2=150
不难发现 2=a[l],5=a[k+1],2=a[r+1]
所以状态转移方程就出来了
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[l]*a[k+1]*a[r+1])
具体代码
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
a[2*n+1]=a[1];
for(int len=2;len<=n;len++){
for(int l=1,r=l+len-1;r<=n*2;l++,r++){
for(int k=l;k<r;k++){
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[l]*a[k+1]*a[r+1]);
}
}
}
for(int i=1;i<=n;i++){
ans=max(ans,dp[i][i+n-1]);
}
