P4850 [IOI2009] 葡萄干 raisins 题解

· · 题解

为了纪念第一道蓝题，特来写一篇题解。

2022.8.25：更改了 LaTeX 格式。

直奔主题：

思路:

显然的，当有一个矩阵满足：

则这个矩阵的最优解为：

如上，是横着切和竖着切的两种情况。

所以，我们可以 dfs 枚举每一刀切的位置。同时，用记忆化删去部分冗余的计算。定义一个数组 f_{a,b,c,d} 进行记忆化搜索。

代码：

#include<bits/stdc++.h>//支持万能头文件！！
using namespace std;
int n,m;
int ra[60][60];         //每块巧克力上的葡萄干数量
int f[60][60][60][60];  //记忆化
int dfs(int a,int b,int c,int d)    
{
    if(f[a][b][c][d]!=0)//如果已经切过这种情况了
            return f[a][b][c][d];//直接返回 
        if(b==d&&a==c)  return 0;//如果开始点和结束点是同一点,即没法切了，就return
    int ma=1e10;//赋一个极大值，以便后来作min运算
    for(int i=a;i<c;i++)    ma=min(ma,dfs(a,b,i,d)+dfs(i+1,b,c,d));//横着切，即上边加下边
    for(int i=b;i<d;i++)    ma=min(ma,dfs(a,b,c,i)+dfs(a,i+1,c,d));//竖着切，即左边加右边
    for(int i=a;i<=c;i++)
        for(int j=b;j<=d;j++)
            ma+=ra[i][j];//要付出多少葡萄干
    return f[a][b][c][d]=ma;
    /*等价于:
    f[a][b][c][d]=ma;
    return f[a][b][c][d];*/
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ra[i][j];  //循环输入葡萄干
        }
    }
    cout<<dfs(1,1,n,m);
    return 0;
}

这种做法开 O2 就可以 AC 了，但是，作为一个合格的 oier ,我们应该不断追求更好的做法。

优化思路:

因为考虑到每进行一次 dfs，就要算一遍葡萄干的和，所以很自然地想到利用前缀和数组来优化。

每输入一个数，则对其进行前缀和计算。就避免每次搜索都用一个双层循环来计算。

前缀和代码： s_{i.j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}

AC代码：

#include<bits/stdc++.h>//支持万能头文件！！
using namespace std;
int n,m;
int ra[60][60];         //每块巧克力上的葡萄干数量
int f[60][60][60][60];  //记忆化
int cc[60][60];         //前缀和数组
int dfs(int a,int b,int c,int d)    
{

    if(f[a][b][c][d]!=0)//如果已经切过这种情况了
        return f[a][b][c][d];//直接返回 
    if(b==d&&a==c)  return 0;//如果开始点和结束点是同一点,即没法切了，就return
    int ma=1e10;
    for(int i=a;i<c;i++)    ma=min(ma,dfs(a,b,i,d)+dfs(i+1,b,c,d));//横着切，即上边加下边
    for(int i=b;i<d;i++)    ma=min(ma,dfs(a,b,c,i)+dfs(a,i+1,c,d));//竖着切，即左边加右边
    f[a][b][c][d]=ma+cc[c][d]-cc[a-1][d]-cc[c][b-1]+cc[a-1][b-1];
    //这里使用前缀和优化
    return f[a][b][c][d];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ra[i][j];  //循环输入葡萄干
            cc[i][j]=ra[i][j]+cc[i][j-1]+cc[i-1][j]-cc[i-1][j-1];//计算前缀和
        }
    }
    cout<<dfs(1,1,n,m);
    return 0;
}

这样不用 O2 就可以过了！

评测记录

拓展：

不会吧不会吧，不会还有人不知道二维前缀和怎么算吧！

核心代码： s_{i.j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}

其中，s 表示前缀和数组，k 表示原数组。

我们可以用一个图形来理解一下： 整个面积就是 s_{i,j}，s_{i-1,j} 相当于 a+b，s_{i,j-1} 相当于 a+c，k_{i,j} 相当于 d，s_{i-1,j-1}相当于a。

很显然：

\begin{aligned} s_{i,j} &=a+b+c+d \\ &=(a+b)+(a+c)-a+d \\ &=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+k_{i,j} \end{aligned}

当然，这不是严谨的推论，图也不标准，仅供参考。