区间 DP
mydcwfy
·
·
个人记录
区间 DP
1. 分类
- 环形 DP 转线性 DP
- 记录方案数
- 区间 DP + 高精度
- 二维区间 DP
2. 例题
T1：[NOI1995] 石子合并
题目传送门 Luogu
题目传送门 AcWing
是一个模板题，大致思路是 f[i][j]= \max(f[i][k]+f[k+1][j])+a[l][r](i\leq k<j)。
时间复杂度 O(n^3)。
不详细讲了。
T2：环形石子合并
题目传送门 AcWing
和上一题其实没有大区别，只是可以首尾合并。
现在怎么办呢？
首先，我们可以发现，合并完后，一定会有相邻的两个点是没有合并的。
于是，我们可以枚举相邻的两个点，从中间断开，就可以转换成链了。
但是，这个的复杂度为 O(n\times n^3=n^4)，会超时。
怎么优化呢？
我们将整个的环断开，复制一倍在末尾。
按链来计算，我们再枚举起点，f[i][i+n-1] 即为答案。
T3：[NOIP2006] 能量项链
题目传送门 Luogu
题目传送门 AcWing
可能很多同学都会想到贪心，但是是有问题的。
其实还是一个区间 DP，和上一题没有大区别。
考虑边界问题，有一些不同。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=205;
int a[N],f[N][N],n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",a+i);
for (int i=1;i<=n;++i) a[i+n]=a[i];
for (int len=1;len<=2*n;++len)
for (int i=1;i<=2*n-len+1;i++)
{
int j=i+len-1;
if (len==1)
{
f[i][j]=0;
continue;
}
for (int k=i+1;k<j;++k)
f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
}
int res=0;
for (int i=1;i<=n;++i) res=max(res,f[i][i+n]);
printf("%d\n",res);
return 0;
}
```
#### T4：凸多边形的划分
[题目传送门 LOJ](https://loj.ac/p/10149)
看似无从下手。
现在，我们先考虑对于一条边，我们必须找到一个点来使这条边构成一个三角形。
枚举这个点，我们发现可以将整个图转化为三个部分，于是就划分为了三个子问题。
于是，我们就可以区间 DP 了！
具体来说，我们选取 $[L,R]$ 这条边，然后枚举对应的点，然后划分为 $[L,i],[i,R],(L,i,R)$ 三部分。
最后要注意的是，答案很大，需要使用该精度。
#### T5：[NOIP2003] 加分二叉树
[题目传送门 AcWing](https://www.acwing.com/problem/content/481/)
[题目传送门 Luogu](https://www.luogu.com.cn/problem/P1040)
题目本身不难，但是我们要学习区间 DP 的思想。
我们发现，在中序遍历中，左子树一定会根节点的左边，右子树一定在根节点的右边。
于是，我们可以枚举当前的根节点，然后就可以划分为几个了。
$f[i,j]=\max(f[i][k-1]\times f[k+1][j]+a[k])(i<k<j)$。
同时，我们要记录答案的来源。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=35;
ll f[N][N];
int n,g[N][N],a[N];
void print(int l,int r)
{
if (l>r) return;
printf("%d ",g[l][r]);
if (l==r) return;
if (l!=g[l][r]) print(l,g[l][r]-1);
if (r!=g[l][r]) print(g[l][r]+1,r);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
for (int len=1;len<=n;++len)
for (int l=1;l<=n-len+1;++l)
{
int r=l+len-1;
ll &val=f[l][r];
if (l==r)
{
val=a[l];
g[l][r]=l;
continue;
}
if (f[l+1][r]+a[l]>=f[l][r-1]+a[r])
{
val=f[l+1][r]+a[l];
g[l][r]=l;
}
else{
val=f[l][r-1]+a[r];
g[l][r]=r;
}
for (int k=l+1;k<r;++k)
{
if (val<f[l][k-1]*f[k+1][r]+a[k])
{
val=f[l][k-1]*f[k+1][r]+a[k];
g[l][r]=k;
}
}
}
printf("%lld\n",f[1][n]);
print(1,n);
return 0;
}
```
#### T6：[NOI1999] 棋盘分割
[题目传送门 Luogu](https://www.luogu.com.cn/problem/P5752)
[题目传送门 AcWing](https://www.acwing.com/problem/content/323/)
首先一阵推导：
$$
ans^2=\dfrac{\sum_{i=1}^{n}(x_i -\overline x)}{n}\\ =\dfrac1n(\sum_{i=1}^n(x_i^2-2x_i\overline x+\overline x^2))
$$
$$
=\dfrac1n(\sum_{i=1}^nx_i^2-2\overline x\sum_{i=1}^nx_i+n \overline x^2)
$$
$$
=\dfrac {\sum_{i=1}^nx_i^2}n-\overline x^2
$$
于是，我们就是要使 $\sum_{i=1}^nx_i^2$ 最小。
首先，分为横切和纵切。
然后，我们还要看是哪一边继续切割，就递归统计答案。
对于另一边，我们可以使用二维前缀和快速计算。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define sqr(x) (x*x)
using namespace std;
const int N=20,M=9,INF=0x3f3f3f3f;
int n=8,k;
int s[M][M];
double f[M][M][M][M][N],X;
inline double get_matrix(int xa,int ya,int xb,int yb)
{
double t=(double)s[xb][yb]-s[xa-1][yb]-s[xb][ya-1]+s[xa-1][ya-1]-X;
return t*t/k;
}
double dp(int xa,int ya,int xb,int yb,int k)
{
double &v=f[xa][ya][xb][yb][k];
if (v>=0) return v;
if (k==1) return v=(get_matrix(xa,ya,xb,yb));
v=1e9;
for (int i=xa;i<xb;++i)
{
v=min(v,(get_matrix(xa,ya,i,yb))+dp(i+1,ya,xb,yb,k-1));
v=min(v,(get_matrix(i+1,ya,xb,yb))+dp(xa,ya,i,yb,k-1));
}
for (int i=ya;i<yb;++i)
{
v=min(v,(get_matrix(xa,ya,xb,i))+dp(xa,i+1,xb,yb,k-1));
v=min(v,(get_matrix(xa,i+1,xb,yb))+dp(xa,ya,xb,i,k-1));
}
// printf("%d %d %d %d %d:%d\n",xa,ya,xb,yb,k,v);
return v;
}
int main()
{
scanf("%d",&k);
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
{
scanf("%d",&s[i][j]);
s[i][j]-=s[i-1][j-1]-s[i][j-1]-s[i-1][j];
}
X=(double)s[n][n]/k;
memset(f,-1,sizeof f);
// printf("%.3lf\n",(double)dp(1,1,n,n,k));
printf("%.3lf\n",sqrt(dp(1,1,n,n,k)));
return 0;
}
```