【HNOI2003】【BZOJ1218】激光炸弹

            

problem

给出n个点,每个点有一个价值,问一个边长为r的正方形最大能覆盖多大价值。

solution

维护二维前缀和即可,复杂度O(n^2)

注意代码容易被卡:
MLE:空间太大,只能比5000大一点。以及前缀和开成一个,不要用两个数组。
RE:空间太小,,不要开5001这样,,x++,y++后会卡点

codes

#include
#include
using namespace std;
const int maxn = 5010;
int n, m, r, c, a[maxn][maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    r = c = m;
    for(int i = 1; i <= n; i++){
        int x, y, z;
        cin>>x>>y>>z;
        x++; y++;//题目0开始。
        a[x][y] = z;
        r = max(r, x); c = max(c, y);
    }
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
    int ans = 0;
    for(int i = m; i <= r; i++)
        for(int j = m; j <= c; j++)
            ans = max(ans, a[i][j]-a[i-m][j]-a[i][j-m]+a[i-m][j-m]);
    cout<'\n';
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像