AtCoder Beginner Contest 419 vp

AtCoder Beginner Contest 419

Subarray Sum Divisibility

考虑滑动窗口的思想，当往后移动时数组的总和会减去$A_i$并加上$A_{i+L}$，题目要求最终的结果满足是K的倍数，那么$A_i$与$A_{i+L}$一定同余于M，因此可以将数组划分为L组，每组要求同余。

这里还需保证长度为L的子序列总和是M的倍数，那么令$dp_{ij}$表示前i组的总和模M为j时所需的最小操作次数，因为一组的元素都是同余的，所以这里可以把i看作是前L个元素中的第i个，只要考虑前i个就能处理所有的。

n,m,l=RR()
nums=RR()

# 用于记录每一组同余于j时所需的操作次数
f=[[0]*m for _ in range(l+1)]
# 前i组的总和模M为j时所需的操作
dp=[[inf]*m for _ in range(l+1)]

# 预处理
for i in range(1,l+1):# 组数
    for j in range(m):# 余数
        for idx in range(i-1,n,l): #元素位置
            f[i][j]+=(j-nums[idx]+m)%m

# 初始化
dp[0][0]=0

for i in range(l):
    for j in range(m):
        # 刷表法，枚举每组变同余于k
        for k in range(m):
            dp[i+1][(j+k)%m]=min(dp[i+1][(j+k)%m],dp[i][j]+f[i+1][k])
print(dp[l][0])