codeforces：A. Writing Code【三维dp + 优化一维】

分析

n个coder写m行代码
第i个coder会在一行代码产生a[i]个bug
求有多少种方案使得bug不超过b个
f[i][j][k]：前i个程序员，写j行代码，产生k个bug的方案
f[0][0][0] = 1 初始
f[i][j][k] = f[i-1][j][k] + f[i][j - 1][k - a[i]] (不写 or 写)

ac code

import sys
input = sys.stdin.readline

def solve():
    n, m, b, mod = list(map(int, input().split()))
    a = list(map(int, input().split()))
    #  n个程序员，m行代码
    # 第i个程序员在一行代码会产生a[i]个bug
    # 多少种方案使得总bug数不超过b个
    # f[i][j][k]：前i个程序员，写j行代码，产生k个bug的方案
    # f[0][0][0] = 1 初始
    # f[i][j][k] = f[i-1][j][k] + f[i][j - 1][k - a[i]] (不写 or 写)
    # 第一个维度优化
    f = [[0] * (b + 1) for _ in range(m + 1)]
    # init
    f[0][0] = 1
    for i in range(n):
        for j in range(1, m + 1):
            for k in range(a[i], b + 1):
                f[j][k] = (f[j][k] + f[j - 1][k - a[i]]) % mod
    ans = 0
    for val in f[m]:
        ans = (ans + val) % mod
    #print(f)
    print(ans)






if __name__ == '__main__':
    solve()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

总结

这种dp去掉一个维度的方法要学会，不然可能会爆空间
注意的是k的取值范围，是在a[i] -> b这个尤其重要