作者:才女与尔同销万古愁 | 来源:互联网 | 2023-08-27 09:57
题目大意:天空上有n颗星星,每颗星星都有其自己的坐标(x,y)和初始发光值s,对于所有星星都有共同的最大的发光值c。
现在给出q段询问,分别给出时刻t,矩形的左下角坐标(x1,y1),右上角坐标(x2,y2),求在t时刻后该矩形内所能看到
的发光值总和。
发光值计算方法&#xff1a;对于T时刻某一星星有发光值s1&#xff0c;在T&#43;1时刻时&#xff0c;如果s1&#43;1<&#61;c&#xff0c;则发光值为s1&#43;1&#xff0c;否则为0&#xff0c;
依次循环递推。
在矩形内或矩形边界上的星星都算在所求的总和内。
题目分析&#xff1a;一开始做得时候没有考虑到可以有多个星星有共同的坐标..WA掉了&#xff0c;比赛完后看讨论知道后再改发现暴力写法T了.....
后来参考官方题解发现竟然是道DP题....orz.....
状态转移方程的话是C[p][x][y]&#43;&#61;C[p][x][y-1]&#43;C[p][x-1][y]-C[p][x-1][y-1]&#xff0c;其中p是发光值&#xff0c;计算完后C[p][x][y]保持得是其左下方
这一块矩形的发光值为p的星星总数。
后来计算得时候同样是查询矩形块内各发光值的星星总数&#xff0c;然后进行相应的相乘得解&#xff08;可以简单的画个坐标系理解一下&#xff09;
#include
#include
#include
#include