AtCoder Beginner Contest 417 vp

AtCoder Beginner Contest 417

Development(有修改floyd)

观察本题的数据范围，可以发现，对于小于等于1000的初始值无论如何变化一定不会大于1000——因为每次增减的值都控制在500以内，小于等于500时会增大，大于则会减小，因此只要初始值小于等于1000就可以结合N的范围求解。令f[i][j]为心情值为j，在第i个值时最终的心情值，递推关系十分明显。如果初始心情大于1000，那么一定会不断减小直到<=1000，可以通过前缀和快速求解得到对应的位置。

n=R()
nums=[RR() for _ in range(n)]
b=[x[-1] for x in nums]
# 前缀和
pre=get_pre(b)

# 动态规划
f=[[inf]*1010 for _ in range(n)]

# 预处理
for p in range(1010):
    if p<=nums[-1][0]:
        f[-1][p]=p+nums[-1][1]
    else:
        f[-1][p]=max(0,p-nums[-1][2])
# 递推
for i in range(n-2,-1,-1):
    for p in range(1010):
        if p<=nums[i][0]:
            f[i][p]=f[i+1][p+nums[i][1]]
        else:
            f[i][p]=f[i+1][max(0,p-nums[i][2])]

for _ in range(R()):
    x=R()
    idx=0
    # 大于，查找什么时候会小于等于1000
    if x>1000:
        idx=bisect_left(pre,x-1000)
        # 太大了会一直减小，直接特判求解
        if idx>=n:
            print(x-pre[-1])
            continue
        x-=pre[idx]
    ans=f[idx][x]
    print(ans)