家居网站页面设计图片,ui培训时间,网站有必要备案吗,百度网站怎么做信息激光炸弹#xff08;BZOJ1218#xff09; 一种新型的激光炸弹#xff0c;可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N10000)个目标#xff0c;用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置#xff0c;每个目标都有一个价值。激光炸弹的投放是…激光炸弹BZOJ1218 一种新型的激光炸弹可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N10000)个目标用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置每个目标都有一个价值。激光炸弹的投放是通过卫星定位的但其有一个缺点就是其爆破范围即那个边长为R的正方形的边必须和xy轴平行。若目标位于爆破正方形的边上该目标将不会被摧毁。 输入输出格式 输入文件的第一行为正整数n和正整数R接下来的n行每行有3个正整数分别表示xi,yi,vi 输出文件仅有一个正整数表示一颗炸弹最多能炸掉地图上总价值为多少的目标结果不会超过32767。 输入样例 2 1 0 0 1 1 1 1 输出样例 1 分析 二维数组前缀和一定区间里价值之和 \(S[i,j] S[i-1,j] S[i,j-1]-S[i-1,j-1]A[i,j]\) 边长R的正方形的价值(ij为正方形的右下角) \(P[i,j] S[i,j] - S[i-R,j] - S[i,j-R] S[i-R,j-R]\) 然后枚举正方形右下角找最大值 错误题解(TLE MLE一堆 用于理解) #includeiostream
#define N 50005
using namespace std;
int A[N][N]{0}; //main函数里定义上限719 X 719
int S[N][N]{0};
int P[N][N]{0};int main(){int n,r,a,b,m;cinnr;m 0;while(n--){int x,y,v;cinxyv;A[x][y] v;if(mx) mx;if(my) my;}m (mr5000)?5000:mr;for(int i0;im;i){for(int j0;jm;j){a (i-10)?0:i-1;b (j-10)?0:j-1;S[i][j] S[a][j]S[i][b]-S[a][b]A[i][j];}}int max 0;for(int i0;im;i){for(int j0;jm;j){a (i-r0)?0:i-r;b (j-r0)?0:j-r;P[i][j] S[i][j] - S[a][j] - S[i][b] S[a][b];if(P[i][j]max)maxP[i][j];}}coutmax;return 0;
} 题解 #includeiostream
#define N 50005
using namespace std;
int A[N][N]{0}; int main(){int n,r,a,b,c,m;cinnr;m 0; // 找个上限 缩短下运行时间while(n--){int x,y,v;cinxyv;A[x1][y1] v;if(mx) mx;if(my) my;}m (mr5000)?5000:mr;for(int i1;im;i){for(int j1;jm;j){a (i-10)?0:i-1;b (j-10)?0:j-1;A[i][j] A[a][j]A[i][b]-A[a][b];}}int max 0;for(int i1;im;i){for(int j1;jm;j){a (i-r0)?0:i-r;b (j-r0)?0:j-r;c A[i][j] - A[a][j] - A[i][b] A[a][b];if(cmax)maxc;}}coutmax;return 0;
} 转载于:https://www.cnblogs.com/wendiudiu/p/10762170.html
