问题 D: 寻找子矩阵
时间限制:?1.000?Sec??内存限制:?128 M
题目描述
一个由n行m列构成的矩阵（从上到下对行1到n编号，从左到右对列1到m编号），第i行第j列中有一个正整数Wij。例如下面是一个3行4列的矩阵。
现在从中选取一个p行q列的子矩阵，例如下面黑框中选取的是一个2行3列的子矩阵。
仔细观察会发现，从上面的矩阵中选取2行3列的子矩阵共有4种不同的方法。
现在请你找这样一个子矩阵，满足以下条件：
将子矩阵的q列从左到右编号为1到q，删除子矩阵中所有编号为奇数的列，或者删除子矩阵中所有编号为偶数的列，然后用子矩阵中剩下的数之和减掉子矩阵中被删除的数之和，得到一个结果S，S最大的子矩阵就是我们要找的子矩阵，注意，这样的子矩阵可能有多个。
例如上面黑框中的子矩阵，删除编号为奇数的列（下图1）或删除编号为偶数的列（下图2）。（阴影部分为删除的列）
按照计算规则，图1中剩下的数之和为8，被删除的数之和为9，所以S=－1，图2中
剩下的数之和为9，被删除的数之和为8，所以S=1，也就是说当选择这个子矩阵时，S的最大值为1。当然可以选择其他子矩阵来获取更大的S。
输入
输入共n+1行。
第一行包含4个整数n、m、p、q(1≤n，m≤1000，1≤p≤n，1≤q≤m)，每两个整数之间用一个空格隔开。
接下来n行，每行包含m个整数。第i+1行的第j个整数为Wij(1≤Wij≤100)，表示矩阵中的第i行第j列的数，每两个整数之间用一个空格隔开。
输出
输出共一行，包含一个整数，表示最大的 S。注意不需要输出你选择的子矩阵。?
样例输入?
3 4 2 3 1 5 2 3 2 3 4 2 8 2 4 3
样例输出?
13
提示
当选择如下子矩阵时，S 的值为 13，满足最大。?
用一个前缀列和处理后面的计算，使后面遍历的时候写起来更简便。
主要还是注意下标的运算
#include<iostream>
using namespace std;
int a[1010][1010];
int main()
{
int n,m,p,q;
cin>>n>>m>>p>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>a[i][j];
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)
{
a[i][j]=a[i-1][j]+a[i][j];
}
}
int s=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i+p-1>n||j+q-1>m)continue;
//cout<<i<<" "<<j<<endl;
int ji=0,ou=0;
int ss,tt;
for(int k=j;k<j+q;k++)
{
if(k%2==0)
{
ou+=(a[i+p-1][k]-a[i-1][k]);
}
if(k%2!=0)
{
ji+=(a[i+p-1][k]-a[i-1][k]);
}
} ss=ou-ji;tt=ji-ou;
int aaa=max(ss,tt);
s=max(aaa,s);
}
}
cout<<s;
}