题解：CF1433F Zero Remainder Sum

这道题和 AT_abc248_c 十分类似，于是蒟蒻在这道题的基础上改动了一点，通过了此题。

对于 AT_abc248_c 这道题，设计 dp 状态如下：

f_{i,j}

表示已经选了

i

个数，和的余数为

j

时的最大值。

考虑转移：（假设该选

a_x

）

f_{i,j} = \begin{cases} f_{i,j} & j = 0 \\ \max(f_{i, j}, f_{j - 1, (j - a_x) \bmod d}) & j \ne 0 \end{cases}

那该如何将 AT_abc248_c 转化为这道题呢?

就是对于每一行跑一遍 dp，再把

f_{0,j}

为下一次 dp 初始化为

\min^{\left\lfloor\frac{m}{2}\right\rfloor}_{i = 1} f_{i,j}

。

答案就是

f_{0,0}

。

code：

CPP

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

int n, m, d;
int a[109];

long long f[109][109];

inline void dp(int k) {
    for(int i = 1; i <= n; i++) {
        for(int j = k; j >= 0; j--) {
            for(int r = d - 1; r >= 0; r--) {
                if(!j) f[j][r] = f[j][r];
                else f[j][r] = max(f[j][r], f[j - 1][(r + d - a[i] % d) % d] + a[i]);
            }
        }
    }

    for(int i = 0; i < d; i++) {
        for(int j = 0; j <= k; j ++) {
            f[0][i] = max(f[0][i], f[j][i]);
        }
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> n >> d;

    memset(f, -0x7f, sizeof(f));

    f[0][0] = 0;

    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> a[j];
        }
        dp(n / 2);
    }

    cout << f[0][0];

    return 0;

}

题解：CF1433F Zero Remainder Sum

文章操作

相关推荐

评论

题解：CF1433F Zero Remainder Sum