icon

2018-11-14

USACO Milk Measuring

I was confused by this problem for about a week.

Here's my solution, use DP with two tables to build the solution, then DFS with pruning to recover the path (choice).

/*
ID: mwx36mw2
TASK: milk4
LANG: C++11
*/
// Author: Wenxing Mei
//   Date: 2018-11-10 11:31
#include <bits/stdc++.h>
#ifdef LOCAL
#include <unistd.h>
#endif
using namespace std;
#define rep(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define per(i, b, a) for (int i = (int)b - 1; i >= (int)a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE
int Q, P;
int val[101];
short must[101][20001];
short can[101][20001];

// must(k,v) = min( must(k, v-val[k]), can(k-1, v-val[k]) + 1) // must use val[k]
// val[k] can(k,v) = min( must(k,v), dp(k-1,v) ) // can use val[k]

const int INF = 0x3f3f3f3f;
vi ans, cur;
void dfs(int k, int v) {
  if (k == 0 || v == 0) {
    ans = cur;
    return;
  }

  if (must[k][v] <= can[k][v]) {
    // must use val[k], cause we need the smallest answer
    if (!ans.empty()) { // pruning
      if (ans[cur.size()] < val[k]) return;
    }
    cur.eb(val[k]);
    for (int vv = v - val[k]; vv >= 0; vv -= val[k]) {
      if (can[k - 1][vv] == can[k][v] - 1) dfs(k - 1, vv);
    }
    cur.pop_back();
  } else {
    dfs(k - 1, v);
    // don't use val[k]
  }
}

int main() {
#ifndef LOCAL
  freopen("milk4.in", "r", stdin);
  freopen("milk4.out", "w", stdout);
  ios_base::sync_with_stdio(0), cin.tie(0);
#endif
  cin >> Q >> P;
  val[0] = 0;
  rep(i, 1, P + 1) { cin >> val[i]; }
  sort(val + 1, val + P + 1, greater<int>());
  P = unique(val + 1, val + P + 1) - val - 1;

  memset(must, INF, sizeof must);
  memset(can, INF, sizeof can);

  rep(i, 0, P + 1) must[i][0] = can[i][0] = 0;

  rep(k, 1, P + 1) {
    rep(v, 1, Q + 1) {
      if (v > val[k])
        must[k][v] = min(must[k][v - val[k]], (short)(can[k - 1][v - val[k]] + 1));
      else if (val[k] == v) {
        must[k][v] = 1;
      }
      can[k][v] = min(must[k][v], can[k - 1][v]);
    }
  }
  cout << can[P][Q];
  dfs(P, Q);
  repv(x, ans) cout << ' ' << x;
  cout << '\n';
  return 0;
}

/*
USER: wenxing mei [mwx36mw2]
TASK: milk4
LANG: C++11

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 10584 KB]
   Test 2: TEST OK [0.011 secs, 10400 KB]
   Test 3: TEST OK [0.011 secs, 10552 KB]
   Test 4: TEST OK [0.011 secs, 10584 KB]
   Test 5: TEST OK [0.011 secs, 10432 KB]
   Test 6: TEST OK [0.014 secs, 10432 KB]
   Test 7: TEST OK [0.014 secs, 10528 KB]
   Test 8: TEST OK [0.021 secs, 10564 KB]
   Test 9: TEST OK [0.014 secs, 10268 KB]
   Test 10: TEST OK [0.021 secs, 10532 KB]

All tests OK.
Your program ('milk4') produced all correct answers!  This is your
submission #7 for this problem.  Congratulations!
*/
comments powered by Disqus

search See also