题解 | #小红取数#

这道题的思路与背包问题有些许相似。
转移方程是df[i][(j+arr[i])%k]=max(df[i-1][j]+arr[i],df[i-1][(j+arr[i])%k])。其中df[i][j]表示添加第i个数时对k取模得j的最大和。

在实现时考虑是否能像背包问题一样，仅使用一维数组，通过遍历的顺序来控制其添加数的顺序，以避免重复累加。事实证明不行，因为这个问题中，j==0时对应的位置是随机的，不一定在前或在后，在j++过程中也不一定就对应着下一个位置，可能去到前面。所以无法通过控制正序或逆序遍历的方法来避免重复，只能使用二维数组来完整保存上一状态。
另一个需要注意的问题与背包问题中求刚好装满时的重量类似。要求一个状态刚好满足一个条件时，必须满足它是严格从初始状态转移过来的，在中间不能出现别的状态转移。所以在初始化数组时，必须将df[0][1,2,...k-1]全部初始化成最小的long long值，以保证就算将全部输入的数与其相加都不会得正，同时将df[0][0]初始化为0。这样做保证了最终得结果都是从0%k=0转移过来的，而不会出现别的违规转移情况。最后只要判断df[n][0]即可，为正则有结果，否则无结果。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    long long n, k;
    cin >> n >> k;
    vector<long long> arr(n + 1, 0);
    for(int i = 1;i <= n;i++){
        cin >> arr.at(i);
    }
    vector<long long> temp(k, -9223372036854775808);
    vector<vector<long long>> df(n + 1, temp);
    df.at(0).at(0) = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 0;j < k;j++){
            df.at(i).at((j + arr.at(i)) % k) = max(df.at(i - 1).at(j) + arr.at(i), df.at(i - 1).at((j + arr.at(i)) % k));
        }
    }
    cout << (df.at(n).at(0) > 0 ? df.at(n).at(0) : -1);
}