Home » 國際競賽 » Details

USACO 2015 US Open, Silver Problem 3. Bessie's Birthday Buffet

Category: 國際競賽, 計算機國際競賽 Date: 2017年12月8日下午3:45

原題下載

USACO2015OPEN-S3

答案

(Analysis by Nick Wu)

Start by sorting the patches of the grass in increasing order of quality.

Let? $f (i)$ ?be the maximum energy that we can accumulate if we end at patch? $i$ .

From patch? $i$ , we can compute the minimum distance from patch? $i$ ?to every other patch. Then, for every patch? $j$ ?where patch? $j$ ?has lower quality grass than patch? $i$ , we have that? $f (i) \geq f (j) + q_{j} - E * d (i, j)$ .

It takes linear time to compute this information for a given patch. If we sort all the patches initially in? $O (N \log N)$ , then this process takes? $O (N^{2})$ , which will run in time.

Here is Mark Gordon's code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

#define MAXN 1010

int Q[MAXN];
int DP[MAXN];
int D[MAXN];
vector<int> E[MAXN];

int main() {
  freopen("buffet.in", "r", stdin);
  freopen("buffet.out", "w", stdout);

  int N, ECST;
  cin >> N >> ECST;
  for (int i = 0; i < N; i++) {
    int D;
    cin >> Q[i] >> D;
    for (int j = 0; j < D; j++) {
      int v;
      cin >> v;
      E[i].push_back(v - 1);
    }
  }

  vector<int> PI;
  for (int i = 0; i < N; i++) {
    PI.push_back(i);
  }
  sort(PI.begin(), PI.end(), [&](int x, int y) {
    return Q[x] < Q[y];
  });

  int result = 0;
  for (int i = N - 1; i >= 0; i--) {
    int u = PI[i];

    queue<int> q;
    memset(D, -1, sizeof(D));
    q.push(u);
    D[u] = 0;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int i = 0; i < E[v].size(); i++) {
        int nv = E[v][i];
        if (D[nv] == -1) {
          D[nv] = D[v] + 1;
          q.push(nv);
        }
      }
    }

    int res = Q[u];
    for (int j = 0; j < N; j++) {
      if (D[j] != -1) {
        res = max(res, Q[u] + DP[j] - ECST * D[j]);
      }
    }
    DP[u] = res;
    result = max(result, res);
  }

  cout << result << endl;
  return 0;
}

以上就是關于【USACO 2015 US Open, Silver Problem 3. Bessie's Birthday Buffet】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

【組隊招募】經濟/數模競賽CNEC/IEO/SIC/HiMCM…組隊報名！

NOAI人工智能奧賽 2026-2027 活動章程出爐：新規則必看！