题解 | #[HNOI2003]激光炸弹#

[HNOI2003]激光炸弹

https://ac.nowcoder.com/acm/problem/20032

题意很明确,一个图中有些点有权值,求矩阵覆盖权值最大
很明显是二维前缀和,但是调了半天,细节还是要多考虑

#include<iostream>
using namespace std;
int a[6010][6010],sum[6610][6010];
int main()
{
    int n,r,ans=0;
    cin>>n>>r;
    r--;
    while(n--)
    {
        int x,y,v;
        cin>>x>>y>>v;
        a[x+1][y+1]=v;
    }
    for(int i=1;i<=5010;i++)
        for(int j=1;j<=5010;j++)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

    for(int i=1;i+r<=5010;i++)
        for(int j=1;j+r<=5010;j++)

            ans=max(ans,sum[i+r][j+r]-sum[i+r][j-1]-sum[i-1][j+r]+sum[i-1][j-1]);

    cout<<ans<<endl;
}
全部评论

相关推荐

投递长鑫存储等公司7个岗位
点赞 评论 收藏
分享
点赞 评论 收藏
分享
05-19 19:57
蚌埠学院 Python
2237:Gpa70不算高,建议只写排名,个人技能不在多而在精,缩到8条以内。项目留一个含金量高的,减少间距弄到一页,硕士简历也就一页,本科不要写很多
实习,投递多份简历没人回...
点赞 评论 收藏
分享
07-02 10:44
门头沟学院 C++
码农索隆:太实诚了,告诉hr,你能实习至少6个月
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务