[CF864E] Fire - 背包dp
Description
某人的房子着火了,他想从大火中带走价值总和尽量多的物品,每次他只能带走一个,分别给出挽救某物品需要的时间t,该物品开始燃烧的时间d(在d时间开始燃烧就不能再挽救该物品了),该物品的价值p。约束:n(1<=n<=100) ti(1<=ti<=20),di(1<=di<=2000),pi(1<=pi<=20)
Solution
以d为关键字排序,做背包即可
这里学到一种记录方案的偷懒办法,虽然复杂度有点高
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
int f[N];
vector<int> v[N];
int n;
struct item
{
int t;
int d;
int p;
int id;
bool operator<(const item &rhs) const
{
return d < rhs.d;
}
} a[N];
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].t >> a[i].d >> a[i].p;
a[i].id = i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)
{
int t = a[i].t;
int d = a[i].d;
--d;
int p = a[i].p;
int id = a[i].id;
for (int j = d; j >= t; j--)
{
if (f[j - t] + p > f[j])
{
f[j] = f[j - t] + p;
v[j] = v[j - t];
v[j].push_back(id);
}
}
}
int ans = 0;
vector<int> ansv;
for (int i = 0; i < N; i++)
{
if (f[i] > ans)
{
ans = f[i];
ansv = v[i];
}
}
cout << ans << endl;
cout << ansv.size() << endl;
for (auto i : ansv)
cout << i << " ";
cout << endl;
}