@loj - 6039@ 「雅礼集训 2017 Day5」珠宝

@description@
@solution@
@accpeted code@
@details@

@description@

Miranda 准备去市里最有名的珠宝展览会，展览会有可以购买珠宝，但可惜的是只能现金支付，Miranda 十分纠结究竟要带多少的现金，假如现金带多了，就会比较危险，假如带少了，看到想买的右买不到。展览中总共有 N 种珠宝，每种珠宝都只有一个，对于第 i 种珠宝，它的售价为 Ci 万元，对 Miranda 的吸引力为 Vi。Miranda 总共可以从银行中取出 K 万元，现在她想知道，假如她最终带了 i 万元去展览会，她能买到的珠宝对她的吸引力最大可以是多少？

原题传送门。

@solution@

就是个数据范围长得比较奇怪的背包。注意到就 Ci 比较小，所以考虑 Ci 相同的珠宝放在一起转移。

对于某些 Ci = p 的物品，类比多重背包的单调队列做法，我们每次一次性处理模 p 余数相同的 dp 状态。

如果 Vi 相同就是个多重背包，直接用单调队列。

如果 Vi 不相同，肯定先选择 Vi 比较大的。因为它的子问题是使用的单调队列，我们不妨猜想推广的问题有决策单调性。手动验证一下发现的确如此。

所以直接写个决策单调性即可。时间复杂度貌似是 O(K*C*log K)，不过能跑过。

@accpeted code@

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXC = 300;

const int MAXK = 50000;

const int MAXN = 1000000;

vector<int>v[MAXC + 5];

ll s[MAXN + 5], f[2][MAXK + 5];

int N, K, p, q, cnt;

void solve(int l, int r, int opl, int opr) {

	if( l > r ) return ;

	int m = (l + r) >> 1;

	int le = max(opl, m - cnt), ri = min(opr, m);

	int opm = le; ll mx = -1;

	for(int i=le;i<=ri;i++)

		if( mx < f[1][p*i + q] + s[m - i] )

			mx = f[1][p*i + q] + s[m - i], opm = i;

	f[0][p*m + q] = mx;

	solve(l, m - 1, opl, opm);

	solve(m + 1, r, opm, opr);

}

bool cmp(int x, int y) {return x > y;}

int main() {

	scanf("%d%d", &N, &K);

	for(int i=1;i<=N;i++) {

		int C, V; scanf("%d%d", &C, &V);

		v[C].push_back(V);

	}

	for(p=1;p<=MAXC;p++) {

		if( !v[p].size() ) continue;

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

			f[1][i] = f[0][i], f[0][i] = 0;

		cnt = 0, sort(v[p].begin(), v[p].end(), cmp);

		for(int i=0;i<v[p].size();i++)

			cnt++, s[cnt] = s[cnt - 1] + v[p][i];

		for(q=0;q<p;q++) {

			int l = 0, r = (K - q) / p;

			if( l <= r ) solve(l, r, l, r);

		}

	}

	for(int i=1;i<=K;i++)

		printf("%lld%c", f[0][i], i == K ? '\n' : ' ');

}

@details@

没开 long long，率先就白给了一发。

巴特西

@loj - 6039@ 「雅礼集训 2017 Day5」珠宝

@description@

@solution@

@accpeted code@

@details@

最新文章

热门文章