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

原題下載

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?ii?to every other patch. Then, for every patch?j?where patch?j?has lower quality grass than patch?i, we have that?f(i)≥f(j)+qj?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(Nlog?N), then this process takes?O(N2), 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;
}

以上就是關(guān)于【USACO 2015 US Open, Silver Problem 3. Bessie's Birthday Buffet】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

2026五大奧賽中國(guó)隊(duì)斬獲四個(gè)世界第一，全員金牌收官！

【組隊(duì)招募】經(jīng)濟(jì)/數(shù)模競(jìng)賽CNEC/IEO/SIC/HiMCM…組隊(duì)報(bào)名！