Educational Codeforces Round 21E selling souvenirs (dp)

传送门

题意

给出n个体积为wi,价值为ci的物品，现在有一个m大的背包

问如何装使得最后背包内的物品价值最大，输出价值

分析

一般的思路是01背包，但n*v不可做

题解的思路

We can iterate on the number of 3-elements we will take (in this editorial k-element is a souvenir with weight k). When fixing the number of 3-elements (let it be x), we want to know the best possible answer for the weight m - 3x, while taking into account only 1-elements and 2-elements.

To answer these queries, we can precalculate the values dp[w] — triples (cost, cnt1, cnt2), where cost is the best possible answer for the weight w, and cnt1 and cnt2 is the number of 1-elements and 2-elements we are taking to get this answer. Of course, dp[0] = (0, 0, 0), and we can update dp[i + 1] and dp[i + 2] using value of dp[i]. After precalculating dp[w] for each possible w we can iterate on the number of 3-elements.

这道题我还没有真正理解，留坑

trick

代码

#include <cstdio>

#include <iostream>

#include <vector>

#include <set>

#include <map>

#include <cmath>

#include <string>

#include <cstring>

#include <sstream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int Maxm = 300015;

const int Maxw = 3;

int n, m;

ll best[Maxm];

vector <int> seq[Maxw];

ll Solve()

{

	int i = 0, j = 0;

	ll cur = 0, w = 0;

	ll res = best[m];

	if (i < seq[0].size() && 1 <= m) res = max(res, seq[0][i] + best[m - 1]);

	while (i + 2 <= seq[0].size() || j + 1 <= seq[1].size()) {

		if (i + 2 <= seq[0].size() && (j + 1 > seq[1].size() || seq[0][i] + seq[0][i + 1] > seq[1][j])) {

			cur += seq[0][i] + seq[0][i + 1]; w += 2; i += 2;

		} else {

			cur += seq[1][j]; w += 2; j++;

		}

		if (w <= m) res = max(res, cur + best[m - w]);

		if (w + 1 <= m) {

			if (i < seq[0].size()) res = max(res, cur + ll(seq[0][i]) + best[m - w - 1]);

			if (i > 0 && j < seq[1].size()) res = max(res, cur + ll(seq[1][j]) - ll(seq[0][i - 1]) + best[m - w - 1]);

		}

	}

	return res;

}

int main()

{

	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {

		int w, c; scanf("%d %d", &w, &c);

		seq[w - 1].push_back(c);

	}

	for (int i = 0; i < Maxw; i++)

		sort(seq[i].rbegin(), seq[i].rend());

	ll cur = 0;

	for (int i = 0; i < seq[2].size(); i++) {

		cur += seq[2][i];

		best[3 * (i + 1)] = cur;

	}

	for (int i = 0; i + 1 <= m; i++)

		best[i + 1] = max(best[i + 1], best[i]);

	printf("%I64d\n", Solve());

	return 0;

}

巴特西

Educational Codeforces Round 21E selling souvenirs (dp)

传送门

题意

分析

trick

代码

最新文章

热门文章