HBC237191[ZJOI2015]地震后的幻想乡,状压dp,概率dp,动态规划target题解

庄子墨算法基础篇 2023-11-16 19:14:01 56 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

PaiGuDragonparticipated in a target training and shot n shots in total. The iii th shot hit the points (xi,yi)(x_i, y_i)(xi,yi) in the Cartesian coordinate system, (xi,yix_i, y_ixi,yi are integers).

PaiGuDragon participated in a target training and shot n shots in total. The iii th shot hit the points (xi,yi)(x_i, y_i)(xi,yi) in the Cartesian coordinate system, (xi,yix_i, y_ixi,yi are integers). The evaluation methods of training results are as follows: Given strictly monotonically increasing sequences d1,d2...,dkd_1,d_2...,d_kd1,d2...,dk and strictly monotonically decreasing sequences score1,score2,...,scorekscore_1, score_2,..., score_kscore1,score2,...,scorek The bull's-eye coordinates are (cx,cy)(cx, cy)(cx,cy), where cx,cycx, cycx,cy are also integers. For the position (xi,yi)(x_i, y_i)(xi,yi) in the iii th shot, find the Manhattan distance between (xi,yi)(x_i, y_i)(xi,yi) and (cx,cy)(cx, cy)(cx,cy) * If PaiGuDragon miss the target, i.e. ∣xi−cx∣+∣yi−cy∣>dk|x_i - cx| + |y_i - cy| > d_k∣xi−cx∣+∣yi−cy∣>dk, lll points will be deducted * Otherwise, score1,scrore2,...,scorekscore_1, scrore_2,...,score_kscore1,scrore2,...,scorek from inside to outside, that is, find the smallest jjj such that ∣xi−cx∣+∣yi−cy∣≤dj|x_i - cx| + |y_i - cy| le d_j∣xi−cx∣+∣yi−cy∣≤dj, and then get scorejscore_jscorej points. The PaiGuDragon was very disappointed with his result, so he decided to redefine the position of the bull's-eye and seek the maximum score. Please help him calculate the maximum scores he can get after redefine the position of the bull's-eye.