RUPC 2016 Day1 D: Scanner

問題

AIZU ONLINE JUDGE

解法

愚直DP

コード

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

typedef long long ll;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll N;
  cin >> N;
  vector<int> T(N);
  T.resize(N);
  for (int i = 0; i < N; ++i) cin >> T[i];
  sort(T.begin(), T.end());
  int sum = accumulate(T.begin(), T.end(), 0);

  const int S = 900;
  vector<vector<vector<bool>>> dp(
      N + 1, vector<vector<bool>>(S, vector<bool>(S, false)));
  dp[0][0][0] = true;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < S; ++j) {
      for (int k = j; k < S; ++k) {
        if (!dp[i][j][k]) continue;
        if (j + T[i] < S)
          dp[i + 1][j + T[i]][k] = dp[i + 1][j + T[i]][k] || dp[i][j][k];
        if (k + T[i] < S)
          dp[i + 1][j][k + T[i]] = dp[i + 1][j][k + T[i]] || dp[i][j][k];
        dp[i + 1][j][k] = dp[i + 1][j][k] || dp[i][j][k];
      }
    }
  }

  int mi = 10000;
  for (int j = 0; j < S; ++j) {
    for (int k = j; k < S; ++k) {
      if (dp[N][j][k]) {
        int ma = max(j, k);
        ma = max(ma, sum - j - k);
        mi = min(mi, ma);
      }
    }
  }
  cout << mi << endl;
}