区间 DP 专场：愉快爆炸
T1
题目大意
有 \(n\) 个有颜色的块，连续 \(k\) 个相同颜色的就可以消掉
现在可以在任意位置插入任意颜色的方块，问最少插入多少个可以全部抵消
题解
先把连续的化成一块，问题变为如何消掉一块。 \(num\) 为个数， \(color\) 为颜色
设 \(F_{i,j,len}\) 表示表示 \([i,j]\) 后面有 \(len\) 个和 \(j\) 颜色一样的与 \(j\) 一起消除。
初始 \(F_{i,i,len}=\max(0,k-num_i-len)\)
然后 \(F_{i,j,len}=F_{i,j-1,0}+\max(0,k-num_j-len)\) 即单独消去
枚举中转点 \(k'\) ，\(F_{i,j,len}=\min_{k'=i}^{j-1}F_{i,k',\min(k,len+num_j)}+F_{k+1,j-1,0} (color_j=color_{k'})\)
就是先消掉 \([k+1,j-1]\) 然后再将第 \(j\) 块与 \(i,k\) 一起操作
目标： \(F_{1,n,0}\)
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,K,x[N],cl[N],w[N],tot;
int f[N][N][10];
int main() {
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)scanf("%d",&x[i]);
cl[1]=x[1],w[1]=tot=1;
for(int i=2;i<=n;i++) {
if(x[i]^x[i-1]) {
++tot,cl[tot]=x[i],w[tot]=1;
} else ++w[tot];
}
memset(f,100,sizeof(f));
n=tot;
for(int i=1;i<=n;i++)
for(int l=0;l<=K;l++)
f[i][i][l]=max(0,K-w[i]-l);
for(int l=2;l<=n;l++)
for(int i=1,j=l;j<=n;i++,j++)
for(int le=0;le<=K;le++) {
f[i][j][le]=f[i][j-1][0]+max(0,K-w[j]-le);
for(int k=i;k<j;k++)
if(cl[j]==cl[k])
f[i][j][le]=min(f[i][j][le],f[i][k][min(le+w[j],K)]+f[k+1][j-1][0]);
}
printf("%d",f[1][n][0]);
return 0;
}
总结
这道题想到了 \(\text{dp}\) 却没有想到区间，更没有想到多设 \([len]\) 这一维
下次要学会通过多一个状态处理转移的错误
T2
题目大意
给你 \(n\) 个 \(a_i\times b_i\) 的矩阵，问乘在一起最少要多少次乘法
输入确保能够相乘
题解
因为输入确保能够相乘，其实就是一个区间 \(\text{dp}\)
枚举中转点 \(k\) 时，这个区间 \([i,j]\) 的贡献是 \(x_i\cdot y_k\cdot y_j\)
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,x[N],y[N],f[N][N];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
for(int l=2;l<=n;l++)
for(int i=1,j=l;j<=n;i++,j++) {
f[i][j]=2100000000;
for(int k=i;k<=j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+x[i]*y[k]*y[j]);
}
printf("%d",f[1][n]);
}
总结
这题以为是贪心，因为没有认真想提示的含义
T3
题目大意
给你一圈数，取一个数的贡献是这个数和其左边、右边的数的积
最后拿完只有两个数，问最大得分和最小得分的差
题解
- 断环成列
- 枚举区间 \([i,j]\) 中的最后取得数 \(k\in[i,j)\) 那么贡献为 \(a_i\cdot a_{k+1}\cdot a_{j+1}\)
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,x[N],f[N][N],g[N][N];
int mx,mn=2100000000;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&x[i]),x[i+n]=x[i];
for(int l=2;l<=n;l++) {
for(int i=1,j=l;j<=(n<<1);i++,j++) {
f[i][j]=2100000000;
for(int k=i;k<j;k++) {
g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+x[i]*x[k+1]*x[j+1]);
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+x[i]*x[k+1]*x[j+1]);
}
}
}
for(int i=1;i<=n;i++)
mx=max(mx,g[i][i+n-2]),
mn=min(mn,f[i][i+n-2]);
printf("%d",mx-mn);
}
总结
这题不知道如何计算贡献，多想想状态的含义
T4
题目大意
\(n\) 个整数组成的圆环，\(i,j\) 的距离为两个格子之间的格子数的最小值
有一个开始指向 1 的指针，取一个数的代价即这个数的值
开始可取下指针所指的那个数以及与这个格子距离小于 \(k\) 的数
可以转动，每次转由一个格子转向其相邻的格子，且代价为圆环上还剩下的数的最大值
题解
所有各自都是要取得，至少需要 \(\sum_{i=1}^n a_i\)
开始可以取走距离小于 \(k\) 的，就是 \([1,k+1],[k,n]\) 全都没了
问题变成一个取完所有数的最小花费，用区间 \(DP\)
设 \(f_{i,j}\) 为从 \(i\) 取到 \(j\) 的最小话费，所以 \(f_{i,j}\ne f_{j,i}\)
区间最大可以预处理为 \(mx_{i,j}\)
\(f_{i,j}=\min(f_{i+1,j}+mx_{i,j},f_{j-1,i}+(len[1,i]+len[j,n])*mx_{i,j})\)
\(f_{i,j}=\min(f_{i-1,j}+mx_{i,j},f_{j+1,i}+(len[1,j]+len[i,n])*mx_{i,j})\)
就是一种正来一种反来
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,K,ans,x[N],f[N][N],mx[N][N];
int main() {
scanf("%d%d",&n,&K);
memset(f,100,sizeof(f));
for(int i=1;i<=n;i++) {
scanf("%d",&x[i]);
ans+=x[i];
mx[i][i]=f[i][i]=x[i];
}
if(n<=K+K+1)return printf("%d",ans),0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
mx[i][j]=mx[j][i]=max(mx[i][j-1],x[j]);
for(int l=1;l<n-K-K;l++) {
for(int i=K+2,j=i+l;j<=n-K;i++,j++)
f[i][j]=min(f[i+1][j]+mx[i][j],f[j-1][i]+(i-K-1 + n-K-j)*mx[i][j]);
for(int i=n-K,j=i-l;j>=K+2;i--,j--)
f[i][j]=min(f[i-1][j]+mx[i][j],f[j+1][i]+(j-K-1 + n-K-i)*mx[i][j]);
}
ans+=min(f[n-K][K+2],f[K+2][n-K]);
printf("%d",ans);
}
总结
这道题确实是比较好，要学会转换问题
End
这次区间 \(dp\) 给本蒟蒻敲响警钟，要注意了