제출 #1071845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071845		VectorLi	Knapsack (NOI18_knapsack)	C++17	100 / 100	55 ms	3752 KiB

knapsack

#include <bits/stdc++.h>
#define long long long

using namespace std;

/*
优美二进制分组 
nklogk
*/

const int K = 2000;
const int MIN = numeric_limits<int>::min();

int n, k; 
long f[K + 1];
vector<pair<int, int>> a[K + 1];

void solve() {
	cin >> k >> n;
	for (int i = 0; i < n; i++) {
		int v, w, c;
		cin >> v >> w >> c;
		a[w].push_back({v, c});
	}
	
	fill(f + 1, f + K + 1, MIN);
	for (int w = 1; w < k + 1; w++) {
		if (a[w].empty()) {
			continue;
		}
		sort(a[w].begin(), a[w].end(), greater<pair<int, int>>());
		// 解释一下为什么是 < k
		// j 相当于已经选择了几个 w 体积的物品
		int i = 0; 
		for (int j = 0; j * w < k; j++) {
			for (int x = k; x >= w; x--) {
				if (f[x - w] > MIN) {
					f[x] = max(f[x], f[x - w] + a[w][i].first);
				}
			}
			a[w][i].second = a[w][i].second - 1;
			if (a[w][i].second == 0) {
				i = i + 1;
			}
			if (i == (int) a[w].size()) {
				break;
			}
		}
	}
	cout << *max_element(f, f + k + 1) << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27