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; }