DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 D - DDPC特別ビュッフェ
解法
まず部分点解法を考えてみます。
K == 1 の場合は, O(NM) で処理すれば大丈夫です。
K > 1 の場合は,
- 2 回の操作で交換をなかったことにする
- 1 回の操作で交換をなかったことにする
というテクニックが使える(1 回の操作で交換をなかったことにするのは N=M=1 の時はダメだけど, その場合はどうせ値が一定にしかならないので気にしなくて良い)
なので, B がもともと持っていた料理を A が K 回の交換後に持っている個数は, min(K, N, M) であるとわかります。この問題では, A, B が持つ料理の美味しさの合計は一定なので, A がもつ料理の美味しさの合計がわかれば A, B 二人の幸福度もわかります。
あとは dp で, dp[i][j] = (A が i 個の料理を手放して, 美味しさの合計を j にすることは出来るか) という dp をやります。これは, 以下のようにして出来ます。
K = min(K, min(N, M)); dp[0][asum] = true; for (int i = 0; i < N; i++) { for (int k = K-1; k >= 0; k--) for (int j = MAX_SUM-1; j >= A[i]; j--) { dp[k+1][j-A[i]] |= dp[k][j]; } } for (int i = 0; i < M; i++) { for (int k = 1; k <= K; k++) for (int j = 0; j < MAX_SUM-B[i]; j++) { dp[k-1][j+B[i]] |= dp[k][j]; } }
交換回数を K に限定して, まず A の料理の数を減らしていき, 次に B の料理を使って料理の数を増やしていく, というようなイメージです。ここまでが部分点解法。
満点解法ではなにをするかというと, dp[j] = (美味しさの合計を j にするような, A が手放す料理の個数の集合) とします。
まず, 1 回も交換をしないと dp[asum] = 1 で, それ以外は 0 です(0 回交換は 1<<0 = 1 なので dp[asum] = 1)。
- A が料理を手放すフェイズでは, 美味しさの合計が j になるような数の集合{el}に対して, dp[j-A[i]] は, {el+1} という集合を手放しても 美味しさの合計が j-A[i] になるということなので, dp[j-A[i]] |= dp[j]<<1 となります。
- B が料理を A に渡すフェイズでは, K 回以上交換するのを許してはいけないので, 各 dp の値の, 1<<(K+1) 以上の部分は無視します。その上で, うえと同様に bit 演算をすれば良いです。dp[j+B[i]] |= (dp[j] & (2^(K+1)-1)) >> 1 ですね。
const int MAX_SUM = 60*22222; int A[60], B[60]; ll dp[MAX_SUM]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M, K; cin >> N >> M >> K; for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < M; i++) cin >> B[i]; int asum = 0, bsum = 0; for (int i = 0; i < N; i++) asum += A[i]; for (int i = 0; i < M; i++) bsum += B[i]; ll ans = 0; if (K == 1) { for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { ans = max(ans, (ll)(asum-A[i]+B[j]) * (bsum-B[j]+A[i])); } cout << ans << endl; return 0; } K = min(K, min(N, M)); dp[asum] = 1; for (int i = 0; i < N; i++) { for (int j = A[i]; j < MAX_SUM; j++) { dp[j-A[i]] |= dp[j]<<1; } } for (int i = 0; i < M; i++) { for (int j = MAX_SUM-B[i]; j >= 0; j--) { dp[j+B[i]] |= (dp[j] & ((1ll<<(K+1))-1)) >> 1; } } for (int i = 0; i < MAX_SUM; i++) { if (dp[i]&1) ans = max(ans, (ll)i*(asum+bsum-i)); } cout << ans << endl; return 0; }