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

题目地址：https://www.luogu.com.cn/problem/P4850 题解原地址：https://createsj.blog.luogu.org/solution-p4850

题目地址：https://www.luogu.com.cn/problem/P4850

题解原地址：https://createsj.blog.luogu.org/solution-p4850

更好的阅读体验？不存在的！

---

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

状态转移方程很容易推出来。设问题给出的矩阵为 \(\textbf A\)，其有一子矩阵，左上角坐标为 \((x_1,y_1)\) ，右下角坐标为 \((x_2,y_2)\) ，那么当只考虑这个子矩阵时，最优解为将该子矩阵切开后的两个矩阵的最优解的最小值与该子矩阵的各元素之和，即

\[ f_{x_1,y_1,x_2,y_2}=min_{x_1,y_1,x_2,y_2}+\sum\limits_{i=x_1}{x_2}\sum\limits_{j=y_1}^{y_2}\textbf A(i,j). \]

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

容易想到，我们应该枚举每个行数和列数不都为 \(1\) 的子矩阵，并保证该子矩阵的任意子矩阵都已得出最优解。为了方便实现，我们设一子矩阵左上角坐标为 \((i,j)\) ，有 \(k\) 行 \(l\) 列，那么当只考虑这个子矩阵时，最优解为

\[ f_{i,j,k,l}=min_{i,j,k,l}+\sum\limits_{x=1}^k\sum\limits_{y=1}^l\textbf A(x+i,y+j). \]

这个状态转移方程与上面的等价，但能方便我们用 DP 实现。

至于求子矩阵各元素之和，我们可以利用前缀和的思想，用 \(sum_{i,j}\) 表示左上角坐标为 \((1,1)\) ，右下角坐标为 \((i,j)\) 的子矩阵各元素之和，那么左上角坐标为 \((i,j)\) 的 \(k\) 行 \(l\) 列的子矩阵各元素之和为

\[ \sum\limits_{x=1}^k\sum\limits_{y=1}^l\textbf A(x+i,y+j)=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}\) 。

核心代码如下：

// 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]=min+sum[i+k][j+l]-sum[i+k][j]-sum[i][j+l]+sum[i][j];
                }

不用开 O2 就可以过，评测记录证明一切。

原文链接:https://www.cnblogs.com/createsj/p/solution-p4850.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有