这无疑是一个分组背包问题,斜率是分组的依据,组内物品则是这个斜率下金块的价值与重量的前缀和。
发现很多人的都是用的double储存斜率,其实我们可以用分数的方法保存,这就需要一个gcd。
然后我们用map套map维护这个分数的分子与分母,这里x,y较小,可以直接用数组来的。
另外我们还需要知道金块的先后关系,由于这个斜率已经确定了,用曼哈顿距离其实和欧几里得距离是一样的。我们这里直接用更方便的曼哈顿距离。然后我们就用set存这个斜率下的全部金块。
看代码的话我是还套个pair,first是曼哈顿距离,second是对应的v,w数组的下标(其实你也可以把(v_i,w_i)再用个pair套进去)。
这样我们就打了个 map套map套set套pair
然后就是简单的分组背包问题了。
话说我搞了这么多的STL,速度居然还行40ms,排前几
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
using namespace std;
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
map<int, map<int, set<pair<int, int>>>> G;
const int N = 4e3 + 128;
const int T = 4e4 + 128;
int w[N], v[N];
vector<vector<pair<int, int>>> Task;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, t;
cin >> n >> t;
for (int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y;
cin >> w[i] >> v[i];
int _gcd = gcd(x, y);
G[x / _gcd][y / _gcd].insert(make_pair(abs(x) + y, i));
}
for (auto i : G)
{
for (auto j : i.second)
{
int tot_w = 0, tot_v = 0;
vector<pair<int, int>> temp;
for (auto k : j.second)
{
tot_w += w[k.second];
tot_v += v[k.second];
temp.push_back(make_pair(tot_w, tot_v));
}
Task.emplace_back(temp);
}
}
static int f[T];
int ans = 0;
for (auto i : Task)
{
for (int j = t; j >= 0; j--)
{
for (auto k : i)
{
if (j - k.first < 0)
continue;
f[j] = max(f[j], f[j - k.first] + k.second);
ans = max(ans, f[j]);
}
}
}
cout << ans << endl;
return 0;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!