BZOJ1218:|BZOJ1218: [HNOI2003]激光炸弹

题意很好理解,在这里就不再叙述。
对于这道题,我们可以直接用二维前缀和来做
设f[i][j]表示从1,1到i,j这个矩形的总和
则有f[i][j] = f[i-1][j] + f[i][j-1] + x - f[i-1][j-1]
BZOJ1218:|BZOJ1218: [HNOI2003]激光炸弹
文章图片

对于所求矩形(即右下角黑色的),则如图所示用整个大矩形-两个红色的矩形+蓝色矩形。
【BZOJ1218:|BZOJ1218: [HNOI2003]激光炸弹】理解了二维前缀和
那么这道题就可以做了。
暴力枚举正方形右下角即可。

#include #include using namespace std; int a[5002][5002]; int x,y,w; int ans; int main() { int n,r; cin>>n>>r; for(int i=1; i<=n; ++i) { cin>>x>>y>>w; a[x+1][y+1]=w; } for(int i=1; i<=5001; ++i) for(int j=1; j<=5001; ++j) a[i][j]=a[i-1][j]+a[i][j-1]+a[i][j]-a[i-1][j-1]; for(int i=0; i<5001-r; ++i) for(int j=0; j<5001-r; ++j) ans=max(ans,a[i+r][j+r]-a[i+r][j]-a[i][j+r]+a[i][j]); cout

    推荐阅读