Educational Codeforces Round 21 E: Selling Souvenirs
エディトリアル見て書いたコード。コメントつき
/* エディトリアルのとおりの解法 */ /* 重さ1, 2のsouvenirだけを使ったとき、重さの和がiとする。 このときdp[i]=(x,y,z)は以下の意味。 xはコストの和の最大値 yは重さ1のsouvenirをいくつ使ったか。 zは重さ2のsouvenirをいくつ使ったか。 インデックスのほうにy,zのような情報を持たせないで、最適値の後ろにくっつけてる。 */ tuple<ll, int, int> dp[300001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vll weight(N), cost(N); rep(i, N) { cin >> weight[i] >> cost[i]; } // 重さの種類は3種類しかないのでバケツソートしておく。 vll costByWeight[4]; rep(i, N)costByWeight[weight[i]].push_back(cost[i]); // とりあえず、コストの大きい方から使いたいのでソートしておく。 rep(i, 4)sort(costByWeight[i].rbegin(), costByWeight[i].rend()); FOR(i, 1, M + 1)dp[i] = mt(-1ll, -1, -1); rep(i, M) { ll sumCost; int cnt1, cnt2; tie(sumCost, cnt1, cnt2) = dp[i]; if (sumCost == -1)continue; if (cnt1 < sz(costByWeight[1])) { smax(dp[i + 1], mt(sumCost + costByWeight[1][cnt1], cnt1 + 1, cnt2)); } if (cnt2 < sz(costByWeight[2]) && i + 2 <= M) { smax(dp[i + 2], mt(sumCost + costByWeight[2][cnt2], cnt1, cnt2 + 1)); } } /* maxCost[i]は1,2の重さのsouvenirだけ使ったとき、重さの和がi以下である場合のコストの最大値 */ vector<ll> maxCost(M + 1); rep(i, M) { maxCost[i + 1] = max(maxCost[i], get<0>(dp[i + 1])); } // sumThreeは重さ3のsouvenirのコストの和 ll answer = 0, sumThree = 0; // 重さ3のsouvenirのコストを総当りで固定する for (int i = 0; i <= M && i / 3 <= sz(costByWeight[3]); i += 3) { // 事前に計算したDPをうまく使って、解を更新する smax(answer, sumThree + maxCost[M - i]); if (i / 3 < sz(costByWeight[3])) { sumThree += costByWeight[3][i / 3]; } } cout << answer << endl; }