首页 > 代码库 > P2280 [HNOI2003]激光炸弹

P2280 [HNOI2003]激光炸弹

2024-10-22 13:02:02   210人阅读

P2280 [HNOI2003]激光炸弹

    • 66通过
    • 300提交
  • 题目提供者xmyzwls
  • 标签各省省选2003湖南云端↑
  • 难度普及+/提高
  • 时空限制1s / 128MB

  讨论  题解  

最新讨论更多讨论

  • 正在实验中学培训的亲门
  • 其实我发现你累不累加v的值…
  • 这真的是省选题？？？

题目描述

技术分享

输入输出格式

输入格式：

 

输入文件名为input.txt

输入文件的第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示 xi，yi ，vi 。

 

输出格式：

 

输出文件名为output.txt

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。

 

输入输出样例

输入样例#1：
2 10 0 11 1 1
输出样例#1：
1

分析

二维前缀和，先预处理出前缀和，然后枚举右下角的点，求最大，注意循环初始条件与结束条件

代码

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int a[5010][5010]; 5 int main() 6 { 7     int n,r,ans = 0; 8     scanf("%d%d",&n,&r); 9     for (int x,y,z,i=1; i<=n; ++i)10     {11         scanf("%d%d%d",&x,&y,&z);12         a[x+1][y+1] = z;13     }14     for (int i=1; i<=5001; ++i)15         for (int j=1; j<=5001; ++j)16             a[i][j] = a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];17     for (int i=0; i<5001-r; ++i)    //从0开始 18         for (int j=0; j<5001-r; ++j)19             ans = max(ans,a[i+r][j+r]-a[i+r][j]-a[i][j+r]+a[i][j]);20     printf("%d",ans);    21     return 0;22 }

 

P2280 [HNOI2003]激光炸弹


联系
我们