题解：abc419_e Subarray Sum Divisibility

Problem Statement

You are given a length- integer sequence =().

Your goal is to perform the following operation repeatedly so that for every length- contiguous subarray of , the sum is a multiple of .

• Choose an integer such that , and increase the value of by .

Find the minimum possible number of operations before achieving the goal.

Constraints

• All input values are integers.

题解

终于明白为什么外人觉得打 OI 英语会变好了，
否则像我一样，在读题的时候别人都已经码完了……

1. 题类：最优解问题；
2. 数据范围： 可过；

这两点基本确定了是动态规划，而且有一点复杂，这和性质有关；

接下来考虑性质：

• 根据题意，；
• 根据加法同余，我们可以减去 ；
• 结果为 ；

下面是经验思路：

• 如果说对象之间有强联系，可以考虑划为一个组，统计整个组的影响，比如这里就是 ，然后对于组进行动态规划；
• 这个分组的思维其实在图论中就是“连通块”“强连通缩点”的技巧；
  • 这会大大减少我们不必要的枚举，直接减去了不可能的枝；
  • 同时通过积累的统计，让我们不必每次转移都进行枚举；

所以现在思路就比较明显了：

• 我们根据下标进行分组；
• 同一组内枚举目标余数；
• 到达目标余数的代价之和就是这个组的代价；
• 对于组之间进行 dp，计算出前 个组余数为 的最小代价 ；
• 答案就是 ；

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n, m, l;
int a[MAXN];

int cost[MAXN][MAXN];
int f[MAXN][MAXN];

int main() {
    /*--- fast IO ---*/
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    /*--- In stream---*/
    cin >> n >> m >> l;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    /*---calc cost in group---*/
    for (int i = 1; i <= l; ++i)
        for (int j = 0; j < m; ++j)
            for (int k = i; k <= n; k += l)
                cost[i][j] += (j - a[k] +  m) % m;
    /*---calc cost among groups---*/
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= l; ++i)
        for (int j = 0; j < m; ++j)
            for (int k = 0; k < m; ++k)
                f[i][j] = min(f[i][j], f[i - 1][(j - k + m) % m] + cost[i][k]);
    /*--- Out stream---*/
    cout << f[l][0];
    return 0;
}