题解：AT_abc419_e [ABC419E] Subarray Sum Divisibility

· · 题解

[ABC419E] Subarray Sum Divisibility 题解

题目描述

给定一个长度为 N 的整数序列 A = (A_1, A_2, \dots, A_N)。

你的目标是重复执行操作，使得序列 A 中每一个长度为 L 的连续子数组的和都是 M 的倍数。每次操作可以选择一个整数 i（1 \le i \le N），并将 A_i 的值增加 1。

求实现目标所需的最少操作次数。

解题思路

我们可以发现这个问题其实类似滑动窗口。可以发现一个性质：对于位置 i (1 \le i \le N-L) ，必须有 A_i \equiv A_{i+L} \pmod M 。那么序列其实是由长度为 L 的周期组成的，且每个周期内相同位置的数在模 M 意义下相等。

所以我们只需要确定前 L 个数在模 M 下的值，整个序列的模 M 的值也就确定了。那么就只需要即让 \sum_{i=1}^{L} A_i \equiv 0 \pmod M 即可。

那显然就是一个背包：

  1. 预处理代价：首先计算代价数组 cst_{i,j}，表示将下标模 L 余 i 的所有数都调整到模 M 余 j 所需的最小操作次数,直接暴力算就行。这一步时间复杂度为 O(N \times M)。

  2. 背包：定义 dp_{i,j} 表示考虑前 i 个组（即前 i 个模 L 的余数类），这些组的和模 M 为 j 的最小代价，其实是一个分组背包。状态转移方程为：

    dp_{i,j} = \min_{0 \leq k < M} \left\{ dp_{i-1,\,(j-k) \bmod M} + cst_{i,k} \right\}

    初始化 dp_{0,0} = 0，其余为无穷大。最终答案为 dp_{L,0}。

动态规划部分的时间复杂度为 O(L \times M^2) 。

代码

#include <bits/stdc++.h>
#define int long long
#define maxn 510
using namespace std;
int n,m,l;
int a[maxn];
int cst[maxn][maxn];//表示把下标%l相同的数改为%m余j的最小代价
int dp[maxn][maxn];
signed main(){
    cin >> n >> m >> l;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i <= l;i++){
        for(int k = 0;k < m;k++){
            for(int j = i;j <= n;j += l){
                if(a[j] % m > k){//算代价
                    cst[i][k] += (m - (a[j] % m) + k); 
                }else{
                    cst[i][k] += (k - a[j] % m);
                }
            }   
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1;i <= l;i++){//背包
        for(int j = 0;j <= m;j++){
            for(int k = 0;k < m;k++){
                dp[i][j] = min(dp[i][j],dp[i - 1][((j - k) + m) % m] + cst[i][k]);
            }
        }
    }
    cout << dp[l][0] << endl;
}