AtCoder Beginner Contest 409 补题

AtCoder Beginner Contest 410

Battles in a Row

显而易见的动态规划，但是这里一定要维护的状态太多，数据范围一定会超，一定要去掉一个状态才能满足给定的数据范围求解。

根据题意，击败的怪兽一定是从头开始连续的一段，并且求解的是能击败的怪兽数，那么定义dp[i][j]表示体力和魔力为i和j的情况下，能击败的最多的怪兽数，DP的结果可以指出要访问的是数组的哪一位，如果do[i][j]=x，那么对于当前状态，第x+1个怪兽的数值假设为x,y，那么dp[i+x][j]=dp[i][j]+1，dp[i][j+y]=dp[i][j]+1，初始时显然有dp[0][0]=0

k,m,n=RR()
f=[[0]*(n+1) for _ in range(m+1)]

nums=[]
for _ in range(k):
    nums.append(RR())

for i in range(m+1):
    for j in range(n+1):
        if i:f[i][j]=max(f[i][j],f[i-1][j])
        if j:f[i][j]=max(f[i][j],f[i][j-1])
        x=f[i][j]   

        if x<k:
            l,r=nums[x]
            if i+l<=m:f[i+l][j]=max(f[i+l][j],f[i][j]+1)
            if j+r<=n:f[i][j+r]=max(f[i][r+j],f[i][j]+1)

print(f[m][n])