题解 P2004 【领地选择】

· · 题解

题意大概是说 n\times m 的矩形中找到一个边长为 c 的矩形使它的价值最大。

根据题意，我们可以枚举左上角的坐标，利用边长 c 算出左下、右上、右下角。再暴力枚举价值和，更新答案即可。

时间复杂度：O(nmc^2)

预计得分：50~70 points

程序如下：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1010;

int n,m,c;
int val[N][N],maxx=-inf,wherex,wherey;

int main(){
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%d",&val[i][j]); //输入
    for(int x1=1; x1<=n-c+1; x1++) 
        for(int y1=1; y1<=m-c+1; y1++){  //枚举左上角
            int x2=x1+c-1;
            int y2=y1+c-1;  //计算右下角
            int ans=0;
            for(int i=x1; i<=x2; i++)
                for(int j=y1; j<=y2; j++)
                    ans += val[i][j];
            if(ans>maxx){
                maxx=ans;
                wherex=x1;
                wherey=y1;
            }//更新答案
        }
    printf("%d %d",wherex,wherey);
    return 0;
}

提交上去？？啊，果然70分。沮丧的我们不得不思考优化。

在此之前，我们思考，我们写出的程序到底差在哪儿？？？

请先思考，再往下阅读

原来，我们的程序有些地方算重复了：

- $(1,1)$ 为左上角，$c=2$ 时我们算了$(1,1)+(1,2)+(2,1)+(2,2)$； - $(1,2)$ 为左上角，$c=2$ 时我们算了$(1,2)+(1,3)+(2,2)+(2,3)$； 咦？$(1,2)+(2,2)$ 被我们算重了！对于这种情况，有一个经典的解决方法——预处理。 所以我们考虑用（二维）前缀和优化 下面我们讲一下什么是二维前缀和，建立在一维前缀和之上，我们要求一个矩阵内一个任意的子矩阵的数的和，我们就可以用二维前缀和，我们还是用DP来预处理，状态和一维前缀和差不多，只不过我们多加了一维。 用 $f(i,j)$ 表示 $1,1$ 这个点与 $(i,j)$ 这个点两个点分别为左上角和右下角所组成的矩阵内的数的和，则状态转移方程为： $f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j}

其中 val_{i,j} 表示 (i,j) 这一格的价值。

怎么来的呢？我们画一下图就知道了。

一开始是这样的：f(i,j) 为 0，即图中所有格子都是白色的。

回顾转移方程：f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j}

第一个加的是 f(i,j-1)，所以我们将 (1,1) ~ (i,j-1) 染成黄色，表示加过一次。如上图所示。

此后再加上 f(i-1,j)，但是我们发现两次染色中有一部分是重复染色的。即：(1,1)~(i-1,j-1)，它们被染过两次色，在上图中我们将这一块区域染成棕色。

既然重复计算了，那我们就剪掉，即减去f(i-1,j-1)，此时 (1,1)~(i-1,j-1) 又回归了黄色（即只染过一次色）。我们发现：只需再把 (i,j) 这一格染成黄色，便大功告成了！

即加上：val_{i,j}，如下图：

所以我们用图解证明了转移方程 f(i,j)=f(i,j-1)+f(i-1,j)-f(i-1,j-1)+val_{i,j}

我们看一下实现代码：

for(int i=1; i<=m; i++)
    for(int j=1; j<=n; j++)
        f[i][j]=val[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];

现在只需枚举左上角，根据边长 c 算出左下角，然后用二维前缀和 O(1) 更新。

附 (x_1,y_1) 到 (x_2,y_2) 权值和的计算方法：

f(x_2,y_2)-f(x_2,y_1-1)-f(x_1-1,y_2)+f(x_1-1,y_1-1)

这可以用二维前缀和的定义进行理解，或用图解也行。

完整代码不提供了，其余几篇题解都讲的挺好。