题解 P4850 【[IOI2009]葡萄干raisins】

发表于 | 分类于 ，

既然大家都在用记忆化搜索，那我就来个 DP 题解吧。有了 O2 谁还会用 DP ！

状态转移方程很容易推出来。设问题给出的矩阵为 $\textbf A$ 有一子矩阵，其左上角坐标为 $(x_1,y_1)$ ，右上角坐标为 $(x_2,y_2)$ ，那么当只考虑这个子矩阵时，最优解为
$$
f_{x_1,y_1,x_2,y_2}=\min\left({f_{x_1,y_1,x’,y_2}+f_{x’+1,y_1,x_2,y_2}|x_1\le x’<x_2}\cup{f_{x_1,y_1,x_2,y’}+f_{x_1,y’+1,x_2,y_2}|y_1\le y’<y_2}\right)+\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}a_{i,j}
$$
即将该子矩阵切开后的两个矩阵的最优解的最小值与该子矩阵的各元素之和。

这个很容易用记忆化搜索实现，但应如何 DP 呢？

容易想到，我们应该枚举每个行数和列数不都为 $1$ 的子矩阵，并使该子矩阵的任意子矩阵都已得出最优解。为了方便实现，我们设一子矩阵左上角坐标为 $(i,j)$ ，有 $k$ 行 $l$ 列，那么当只考虑这个子矩阵时，最优解为
$$
f_{i,j,k,l}=\min\left({f_{i,j,c,l}+f_{i+c,j,k-c,l}|1\le c<k}\cup{f_{i,j,k,c}+f_{i,j+c,k,l-c}|1\le c<l}\right)+\sum\limits_{x=i}^{i+k}\sum\limits_{y=j}^{j+l}a_{x,y}
$$
这个状态转移方程与上面的等价，但能方便我们用 DP 实现。

至于求矩阵各元素之和，我们可以利用前缀和的思想，用 $sum_{i,j}$ 表示左上角坐标为 $(1,1)$ ，右上角坐标为 $(i,j)$ 的子矩阵各元素之和，那么左上角坐标为 $(i,j)$ 的 $k$ 行 $l$ 列的子矩阵各元素之和为
$$
sum_{i+k-1,j+l-1}-sum_{i+k-1,j-1}-sum_{i-1,j+l-1}+sum_{i-1,j-1}
$$
为了消去 $-1$，我们设一子矩阵左上角坐标为 $(i+1,j+1)$ ，有 $k$ 行 $l$ 列，那么当只考虑这个子矩阵时，最优解为 $f_{i,j,k,l}$ 。

主要代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//i,j,k,l 的意义已经说明
for(register int i,j,k=1,l,c,xs,ys,min,t;k<=n;++k)
    for(l=1;l<=m;++l)
        if(k!=1 || l!=1)
            for(i=0,xs=n-k;i<=xs;++i)//xs 是为了限制 i，减少运算次数
                for(j=0,ys=m-l;j<=ys;++j)//ys 同理
                {
                    //min 表示将该子矩阵切开后的两个矩阵的最优解的最小值
                    min=0x7fffffff;
                    for(c=1;c<k;++c)
                    {
                        t=f[i][j][c][l]+f[i+c][j][k-c][l];
                        if(t<min)
                            min=t;
                    }
                    for(c=1;c<l;++c)
                    {
                        t=f[i][j][k][c]+f[i][j+c][k][l-c];
                        if(t<min)
                            min=t;
                    }
                    //状态转移方程
                    f[i][j][k][l]=sum[i+k][j+l]-sum[i+k][j]-sum[i][j+l]+sum[i][j]+min;
                }

不用开 O2 就可以过，大家可以看我的评测记录。