求助

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=5010;
   
4. int n,m;
   
5. int w[N][N];
   
6. int s[N][N]; //可以用前缀和表示原数组,凡是前缀和都从1开始，防止边界问题
   
7. int main()
   
8. {
   
9.     int cnt,r;
   
10.     cin>>cnt>>r;
    
11.     r=min(5001,r);
    
12.     n=m=5001;
    
13.     while(cnt--)
    
14.     {
    
15.         int x,y,w;
    
16.         cin>>x>>y>>w;
    
17.         x++,y++; //都往右移一位，向下移动一位  
    
18.         // n=max(x,n);
    
19.         // m=max(y,m);
    
20.         s[x][y]+=w;   //将每个区间的价值进行相加
    
21.     }
    
22.     //预处理前缀和
    
23.     for(int i=1;i<=n;i++)
    
24.     {
    
25.         for(int j=1;j<+n;j++)
    
26.         {
    
27.             s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];   
    
28.         }
    
29.     }
    
30.     int res=0;
    
31.     // 枚举所有边长是r的矩形
    
32.     for(int i=r;i<=n;i++)
    
33.     {
    
34.         for(int j=r;j<=m;j++)
    
35.         {
    
36.             res=max(res,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
    
37.         }
    
38.     }
    
39.     cout<<res<<endl;
    
40.    
    
41.    
    
42.    
    
43. }

复制代码

为什么输出还是0啊

isdkz

问题出在这一行代码上：

1. for(int j=1;j<+n;j++)
   

复制代码

这里应该是  j<=m  而不是  j<+n 。修改后的代码如下：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=5010;
   
4. int n,m;
   
5. int w[N][N];
   
6. int s[N][N]; //可以用前缀和表示原数组,凡是前缀和都从1开始，防止边界问题
   
7. int main()
   
8. {
   
9.     int cnt,r;
   
10.     cin>>cnt>>r;
    
11.     r=min(5001,r);
    
12.     n=m=5001;
    
13.     while(cnt--)
    
14.     {
    
15.         int x,y,w;
    
16.         cin>>x>>y>>w;
    
17.         x++,y++; //都往右移一位，向下移动一位
    
18.         // n=max(x,n);
    
19.         // m=max(y,m);
    
20.         s[x][y]+=w;   //将每个区间的价值进行相加
    
21.     }
    
22.     //预处理前缀和
    
23.     for(int i=1;i<=n;i++)
    
24.     {
    
25.         for(int j=1;j<=m;j++) // 修改此处
    
26.         {
    
27.             s[ i][j]=s[i-1][j]+s[ i][j-1]-s[i-1][j-1];   
    
28.         }
    
29.     }
    
30.     int res=0;
    
31.     // 枚举所有边长是r的矩形
    
32.     for(int i=r;i<=n;i++)
    
33.     {
    
34.         for(int j=r;j<=m;j++)
    
35.         {
    
36.             res=max(res,s[ i][j]-s[i-r][j]-s[ i][j-r]+s[i-r][j-r]);
    
37.         }
    
38.     }
    
39.     cout<<res<<endl;
    
40. }
    

复制代码

这样修改后，输出应该是正确的了。