# P1776 宝物筛选

Luogu-P1776 宝物筛选

## 解法 1：二进制优化

#include <bits/stdc++.h>
using namespace std;
int dp[40005];
int main()
{
int n, W;
scanf("%d%d", &n, &W);
for (int i = 0; i < n; i++) {
int t, c, p;
scanf("%d%d%d", &c, &t, &p);
int tmp = 1;
while (p >= tmp) {
p -= tmp;
for (int j = W; j >= t*tmp; j--)
dp[j] = max(dp[j], dp[j-t*tmp]+c*tmp);
tmp *= 2;
}
if (p == 0) continue;
for (int j = W; j >= t*p; j--) {
dp[j] = max(dp[j], dp[j-t*p]+c*p);
}
}
printf("%d\n", dp[W]);
return 0;
} 

## 解法 2：单调队列优化

$$f[i][j] = max_{0<=k<=m[i]}\{f[i-1][j-k\times w[i]]+k\times v[i]\}$$

$$f[i][j]=max\{f[i-1][(k_1-k)\times w[i]+d]-(k_1-k)\times v[i] \}+ k_1\times v[i]$$

RECORD

#include <bits/stdc++.h>
using namespace std;
int n, W;
int v[105], w[105], m[105];
int dp[105][40004];
struct deq {
int arr[40004];
bool empty() { return head+1 == tail; }
void pop_back() { tail--; }
void push_back(int x) { arr[tail] = x; tail++; }
void clear() { head = 0; tail = 1; }
int front() { return arr[head+1]; }
int back() { return arr[tail-1]; }
} dq;
int main()
{
cin >> n >> W;
int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> m[i];
if (w[i] == 0) {
ans += v[i]*m[i];
continue;
}
for (int j = 0; j < w[i]; j++) { // 余数
dq.clear();
// k 实际上表示的是文中的 k_1
for (int k = 0; j+k*w[i] <= W; k++) {
// dq.front() 实际上表示的是文中的 k_1 - k
while (!dq.empty() && k-dq.front() > m[i]) dq.pop_front();
while (!dq.empty() && dp[i-1][j+dq.back()*w[i]]+(k-dq.back())*v[i] <= dp[i-1][j+k*w[i]]) dq.pop_back();
dq.push_back(k);
if (!dq.empty()) dp[i][j+k*w[i]] = max(dp[i][j+k*w[i]], dp[i-1][j+dq.front()*w[i]]+(k-dq.front())*v[i]);
}
}
}
cout << dp[n][W]+ans << endl;
return 0;
}

2022-08-21 10:12:34 in 题解