题目：BZOJ1218、洛谷P2280。
题目大意：给你一个5000*5000的平面，一些点可能有价值，求边长为r的正方形最多能框住多少价值（正方形的边必须与x、y轴平行）。
解题思路：二维前缀和dp。设dp[i][j]表示(1,1)~(i,j)的总价值，那么dp[i][j]=a[i][j]+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]。
求正方形(i-r+1,j-r+1)~(i,j)的价值和就为dp[i][j]-dp[i][j-r]-dp[i-r,j]+dp[i-r,j-r]。
由于内存的限制，a数组应该直接用dp数组替代，否则你会华丽的MLE！
注意坐标从0开始，所以我给每个x和y都加了1。
时间复杂度$O(5000^2)$。
C++ Code：
#include<cstdio>
#include<cstring>
using namespace std;
int dp[5050][5050];
int main(){
int n,r;
scanf("%d%d",&n,&r);
memset(dp,0,sizeof(dp));
for(;n--;){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
dp[x+1][y+1]=v;
}
for(int i=1;i<5002;++i)
for(int j=1;j<5002;++j)
dp[i][j]=dp[i][j]+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
int ans=0;
for(int i=r;i<5002;++i)
for(int j=r;j<5002;++j){
int p=dp[i][j]-dp[i][j-r]-dp[i-r][j]+dp[i-r][j-r];
if(p>ans)ans=p;
}
printf("%d
",ans);
return 0;
}