P2004 领地选择

P2004 领地选择

题目描述

作为在虚拟世界里统帅千军万马的领袖，小Z认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小T来说是非常重要的。

首都被认为是一个占地C*C的正方形。小Z希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

输入输出格式

输入格式：

第1行：三个正整数N，M，C，表示地图的宽和长以及首都的边长。

第2∼N+1行：第i+1行包含M个整数，表示了地图上每个地块的价值。价值可能为负数。

输出格式：

一行，两个整数X、Y，表示首都左上角的坐标。

输入输出样例

输入样例#1： 复制

3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1

输出样例#1： 复制

1 2

说明

对于60%的数据：N、M≤50。

对于90%的数据：N、M≤300。

对于100%的数据：N、M≤1000，C≤min(N，M)。

这一题就是前缀和呀……为什么会被加到dp里呢？我们先来思考一下要求下图的黑色部分面积，该怎么求呢？

    
枚举右下的这个点，就是(i,j);

很显然，应该是非白色部分减去红、灰色部分再减去蓝灰色部分加上灰色部分（因为灰色被减了两次），那么，我们假设f[i][j]表示从1,1到i,j所有数字之和，那么从i-c,j-c到i,j的值就是

    f[i][j]-f[i-c][j]-f[i][j-c]+f[i-c][j-c];

解到这里，O(mn)的代码就可以构出了，代码如下（别全抄代码，自己动动脑）：

#include<iostream>
#include<cmath>
using namespace std;
int n,m,c,a[1001][1001],f[1001][1001],maxx=-0x7fffffff,x,y;
int main(){
    cin>>m>>n>>c;
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
        scanf("%d",&a[i][j]);  //输入矩阵 
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
         f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1]; //求前缀和（f[i][j]表示1,1到i,j数字之和） 
    for(int i=c;i<=m;i++)
      for(int j=c;j<=n;j++)
        if(f[i][j]-f[i-c][j]-f[i][j-c]+f[i-c][j-c]>maxx){
            maxx=f[i][j]-f[i-c][j]-f[i][j-c]+f[i-c][j-c];  //解释如上 
            x=i-c+1;
            y=j-c+1;
        }
    cout<<x<<" "<<y;
}