AtCoder Beginner Contest 418 vp

AtCoder Beginner Contest 418

Trapezium

对于给定的数据范围，显而易见的可以找出两个点之间的斜率然后组合求解，但是这里会对平行四边形重复求解，因此利用平行四边形对角线中点相同的规则求解删除重复计算的平行四边形，这里对平行四边形的求解也是用组合。

注意哈希表存储分数防止精度问题。

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)