目录

1.99. 激光炸弹 - AcWing题库

2.1230. K倍区间 - AcWing题库

3.1205. 买不到的数目 - AcWing题库

4.2. 01背包问题 - AcWing题库

（1）动归五部曲

（2）y总普通写法

（3）y总终极写法（滚动数组）

5.3. 完全背包问题 - AcWing题库

（1）朴素做法（python超时）

（2）高级做法

（3）滚动数组

6.4. 多重背包问题 I - AcWing题库

（1）朴素做法

1.99. 激光炸弹 - AcWing题库

注意边界

n,r=map(int,input().split())
maxv=4
adj=[[0 for i in range(maxv)]for j in range(maxv)]
maxx,maxy=-1,-1
for i in range(n):
    x,y,w=map(int,input().split())
    x+=1
    y+=1
    if x>maxx:maxx=x
    if y>maxy:maxy=y
    adj[x][y]+=w

for x in range(1,maxx+1):
    for y in range(1,maxy+1):
        adj[x][y] = adj[x][y - 1] + adj[x - 1][y] - adj[x - 1][y - 1] + adj[x][y]
ans=-1
for x in range(1,maxx+1):
    for y in range(1,maxy+1):
        x1,y1=x,y
        x2,y2=min(maxx,x+r-1),min(maxy,y+r-1)
        cur=adj[x2][y2]-adj[x2][y1-1]-adj[x1-1][y2]+adj[x1-1][y1-1]
        if cur>ans:
            ans=cur
print(ans)

2.1230. K倍区间 - AcWing题库

前缀和+优化

n,k=map(int,input().split())
s=[0 for i in range(n+1)]
ans=0
for i in range(1,n+1):
    value=int(input())
    s[i]=s[i-1]+value
cnt=[0 for i in range(k)]
cnt[0]=1
for i in range(1,n+1):
    ans+=cnt[s[i]%k]
    cnt[s[i] % k] += 1
print(ans)

3.1205. 买不到的数目 - AcWing题库

数学题

a,b=map(int,input().split())
print(a*b-a-b)

4.2. 01背包问题 - AcWing题库

（1）动归五部曲

n,maxv=map(int,input().split())
maxv+=1
v,w=[],[]
for i in range(n):
    vi,wi=map(int,input().split())
    v.append(vi)
    w.append(wi)
dp=[[0 for i in range(maxv)]for j in range(n)]
for i in range(maxv):
    if i>=v[0]:
        for j in range(i,maxv):
            dp[0][j]=w[0]
        break
for i in range(1,n):
    for j in range(1,maxv):
        if v[i]<=j:
            dp[i][j]=max(dp[i-1][j],w[i]+dp[i-1][j-v[i]])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

（2）y总普通写法

n,maxv=map(int,input().split())
v,w=[0],[0]
for i in range(n):
    vi,wi=map(int,input().split())
    v.append(vi)
    w.append(wi)
dp=[[0 for i in range(maxv+1)]for j in range(n+1)]
for i in range(1,n+1):
    for j in range(maxv+1):
        dp[i][j]=dp[i-1][j]
        if j>=v[i]:dp[i][j]=max(dp[i][j],w[i]+dp[i-1][j-v[i]])
print(dp[-1][-1])

（3）y总终极写法（滚动数组）

n,maxv=map(int,input().split())
v,w=[0],[0]
for i in range(n):
    vi,wi=map(int,input().split())
    v.append(vi)
    w.append(wi)
dp=[0 for i in range(maxv+1)]
for i in range(1,n+1):
    for j in range(maxv,v[i]-1,-1):
        dp[j]=max(dp[j],w[i]+dp[j-v[i]])
print(dp[-1])

5.3. 完全背包问题 - AcWing题库

（1）朴素做法（python超时）

n,maxv=map(int,input().split())
v,w=[0],[0]
for i in range(n):
    vi,wi=map(int,input().split())
    v.append(vi)
    w.append(wi)
dp=[[0 for i in range(maxv+1)]for j in range(n+1)]
for i in range(1,n+1):
    for j in range(maxv+1):
        for k in range((j//v[i])+1):
            dp[i][j]=max(dp[i][j],k*w[i]+dp[i-1][j-k*v[i]])
print(dp[-1][-1])

（2）高级做法

n,maxv=map(int,input().split())
v,w=[0],[0]
for i in range(n):
    vi,wi=map(int,input().split())
    v.append(vi)
    w.append(wi)
dp=[[0 for i in range(maxv+1)]for j in range(n+1)]
for i in range(1,n+1):
    for j in range(maxv+1):
        dp[i][j]=dp[i-1][j]
        if j>=v[i]:
            dp[i][j]=max(dp[i][j],w[i]+dp[i][j-v[i]])
print(dp[-1][-1])

（3）滚动数组

n,maxv=map(int,input().split())
v,w=[0],[0]
for i in range(n):
    vi,wi=map(int,input().split())
    v.append(vi)
    w.append(wi)
dp=[0 for i in range(maxv+1)]
for i in range(1,n+1):
    for j in range(v[i],maxv+1):
        dp[j]=max(dp[j],w[i]+dp[j-v[i]])
print(dp[-1])

6.4. 多重背包问题 I - AcWing题库

（1）朴素做法

n,maxv=map(int,input().split())
s,v,w=[0],[0],[0]
for i in range(n):
    vi,wi,si=map(int,input().split())
    v.append(vi)
    w.append(wi)
    s.append(si)
dp=[[0 for i in range(maxv+1)]for j in range(n+1)]
for i in range(1,n+1):
    for j in range(maxv+1):
        for k in range((j//v[i])+1):
            if k>s[i]:
                break
            dp[i][j]=max(dp[i][j],k*w[i]+dp[i-1][j-k*v[i]])
print(dp[-1][-1])