0

描述：

杰克正在他的花园里种一些花生。花园是一个长*宽的矩形，每个单位面积都有自己独立的花生数量。他想找出在给定大小的区域中花生的最大数量是多少。该区域的大小固定为 a*b。

输入格式：

第 1 行：2 整数长度 L 和宽度 W

Line 2 - L+1 : 每行W整数，代表单位面积花生的数量，A(0<=A<=10）</p>

Line L+2 : 2个整数，a和b，分别代表选中区域的长宽

输出格式：

一个整数m，即选择的a*b区域内花生数量的最大总和

样本输入：

4 5
1 2 3 4 5
6 7 8 0 0
0 9 2 2 3
3 0 0 0 1
3 3

样本输出

38

数据满足：1≤a≤L，1≤b≤W

我认为这个问题可以抽象为：返回我认为有 (L-a+1)*(W-b+1) 个可能的和的 L*W 数组的 a*b 子数组中数字的最大和我必须找到最大值。

我的代码在这里，它不能给出正确的结果。我的代码总是返回区域左上区域的总和，但实际上问题需要返回所有可能位置中 a*b 区域的 MAXIMUM SUM。提前非常感谢！

#include <iostream>
#include <cstring>
using namespace std;
 
int L,W,a,b,i,j,x,y,p,q,r,s;
 
int main()
{
    cin>>L>>W;
    int peanut[L][W];
    for (i=0;i<L;i++) 
     for (j=0;j<W;j++) 
       cin>>peanut[i][j];
    cin>>a>>b;
 
    int sumArray[L-a+1][W-b+1];
    memset(sumArray,0,(L-a+1)*(W-b+1)*sizeof(int));
     
    for (p=0;p<L-a+1;p++)
     for (q=0;q<W-b+1;q++) 
       {
        for (r=p;r<a;r++)
         for (s=q;s<b;s++) sumArray[p][q]+=peanut[r][s]; 
       }
        
    int max = 0;
    for (x=0;x<L-a+1;x++)
     for (y=0;y<W-b+1;y++) 
       if (sumArray[x][y]>max) max=sumArray[x][y];
    cout << max;
    return 0;
}
4

3 回答 3

1

问题是您没有仔细索引元素来计算sumArray. 我只更改了两行代码以使其正常工作。

for (r=0;r<a;r++)
  for (s=0;s<b;s++) sumArray[p][q]+=peanut[p+r][q+s];

以下是完整代码。如果还有其他问题，请修复它。

#include <iostream>
#include <cstring>
using namespace std;

int L,W,a,b,i,j,x,y,p,q,r,s;

int main()
{
    cin>>L>>W;
    int peanut[L][W];
    for (i=0;i<L;i++) 
     for (j=0;j<W;j++) 
       cin>>peanut[i][j];
    cin>>a>>b;

    int sumArray[L-a+1][W-b+1];
    memset(sumArray,0,(L-a+1)*(W-b+1)*sizeof(int));

    for (p=0;p<L-a+1;p++)
     for (q=0;q<W-b+1;q++) 
       {
        for (r=0;r<a;r++)
         for (s=0;s<b;s++) sumArray[p][q]+=peanut[p+r][q+s]; 
       }

    int max = 0;
    for (x=0;x<L-a+1;x++)
     for (y=0;y<W-b+1;y++) 
       if (sumArray[x][y]>max) max=sumArray[x][y];
    cout << max;
    return 0;
}
于 2013-06-05T16:34:32.963 回答
0

有两个问题。首先，a和b是测试区域的大小。

     for (r=p;r<a;r++)
       for (s=q;s<b;s++) 
          sumArray[p][q]+=peanut[r][s];

在这里，p并q表示初始的缺陷，但是您正在根据子区域维度限制检查索引。相反，它应该是：

     for (r=p;r<p+a;r++)
       for (s=q;s<q+b;s++) 
          sumArray[p][q]+=peanut[r][s];

第二个问题是 38是答案；最左上角的区域包含所有子矩形的最大值。这是我打印所有值的解决方案。需要注意的是，我不熟悉这个int arr[X][Y]业务when Xand Yare not const（无法编译），所以我把它改成了我熟悉的东西。

#include <iostream>
#include <cstring>
using namespace std;

int L,W,a,b,i,j,x,y,p,q,r,s;

int main()
{
    cin>>L>>W;
    int** peanut=new int*[L]; //a new row pointer for each column element
    for (i=0;i<L;i++){ 
     peanut[i]=new int[W]; //the actual row for each column element
        for (j=0;j<W;j++)
            cin>>peanut[i][j];
    }
    cin>>a>>b;

    //don't need to remember results; just compare maximum after each evaluation.
    //int sumArray[L-a+1][W-b+1];
    //memset(sumArray,0,(L-a+1)*(W-b+1)*sizeof(int));

    int max = 0;
    for (p=0;p<L-a+1;++p){
        for (q=0;q<W-b+1;++q){

           int sum=0;
           for (r=p;r<p+a;++r) //r<p ==> r<p+a, prefix increment is always better
               for (s=q;s<q+b;++s){ //s<q ==> s<q+b, prefix increment is always better
                   cout << "(" << r << "," << s << "," << peanut[r][s] << ") ";
                   sum+=peanut[r][s]; 
               }
           cout << sum << endl;
           if(sum>max) max=sum;

        }
    }

    /*  Merged in previous loop
    int max = 0;
    for (x=0;x<L-a+1;x++)
     for (y=0;y<W-b+1;y++) 
       if (sumArray[x][y]>max) max=sumArray[x][y];
    */

    cout << "Answer: " << max;

    //Since I'm in Visual Studio, I need to pause and see the result before quitting...
    int s;
    cin >> s;

    return 0;
}
于 2013-06-05T16:32:14.637 回答
0

问题是这部分：

for (r=p;r<a;r++)
         for (s=q;s<b;s++) sumArray[p][q]+=peanut[r][s];

你没有迭代a和b时间。将其更改为：

for (r=p;r<p+a;r++)
         for (s=q;s<q+b;s++) sumArray[p][q]+=peanut[r][s];
于 2013-06-05T16:34:03.640 回答