题目：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
     
      #include
      
       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\n",ans);	return 0;}