AOJ 3187 Mod Reap (AUPC 2020 day3-C)

DP の添字を mod をとった値にするテクニック

問題へのリンク

問題概要

個の正の整数 が与えられる。これらの中からいくつか選びたい。選んだ整数のスコアを以下で定める。

• 整数の総和を として
• + %

スコアの最大値を求めよ。

制約

• 
• 

考えたこと

そもそも「整数のうちをいくつか選んだ総和」(部分和とよぶ) を考える時点で、それはもう、とりあえず DP を考えるのが典型。というわけで

• dp[ i ][ v ] := 最初の i 個の整数から、いくつか選んだ総和が v となるときのスコアの最大値

としたくなる。しかしこのままでは v が肥大化することがあるので無理。そこで工夫する。

DP の添字を「あまり」にする

これも典型テクニックだが、DP の状態空間を圧縮するテクニックの一つとして、「mod を取った値」にするというものがある。今回はこうする。

• dp[ i ][ r ] := 最初の i 個の整数から、いくつか選んだ整数の総和を M で割ったあまりが r となるようにしたときの、スコアの最大値

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    vector<long long> dp(K, -1), ndp(K, -1);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        ndp.assign(K, -1);
        for (int j = 0; j < K; ++j) {
            if (dp[j] == -1) continue;
            chmax(ndp[j], dp[j]);
            chmax(ndp[(j + A[i]) % K], dp[j] + A[i]);
        }   
        swap(dp, ndp);
    }
    long long res = 0;
    for (int k = 0; k < K; ++k) chmax(res, dp[k] / K - k);
    cout << res << endl;
}