Trade

tag：

背包dp 数学推导超大容量背包
cf分段2100+ 铜牌题左右的背包问题

题意：

给定一些物品和钱s，购买物品数量为k时其他物品的价格会增长
当购买k件物品时，其他物品的价格为x[i] + p[i]*k
求最大购买物品量

很显然能想到是一个背包dp问题，但是数值是一个非常困难的问题。我们发现s其实非常大，所以从这里考虑就知道背包的第二维度肯定不是金钱而是物品个数。

那么问题就转化为了dp[i][j] = k 代表前i个物品中购买了j个物品，此时花费的最小值。

我们这里就要简单证明一下购买的物品在限定金额内不可能无限量购买，就要简单的计算一下按照最劣情况购买k件物品需要多少钱。此时解方程得到k其实是1000左右的数字。此时就可以开始写转移方程了。

dp[i][j] = min(dp[i - 1][j],dp[i - 1][j -  1] + cost);

接下来思考cost的问题。如果所有物品他们的购买优先级是相同时，那么理论上可以随机取物品更新dp。但是这题我们会发现购买物品的优先级是存在不同的。因为当增长数值p[i]太大，他必然是最先被取用的。这里有一个比较显然的贪心。我们接下来就是要将这个显然的贪心转移到动态规划中。

我们假定已知结果存在一组序列满足和小于s，那么这组和的最小值成立当且仅当p按照从大到小排列并购买。

那么对于dp[i][j]来说，在选中第i件物品之前，一共购买了j件物品，其中这j件物品一定是按照p值从大到小排列。那么你取的下一个数只要p小于等于已经取用的j个物品就可以排在第j+1位。

因此只需要非常简单的sort p数组，并将他们从大到小依次放入背包，就能实现上面的递减关系递进。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
const int mod = 998244353;
bool cmp(pair<ll, ll >a, pair<ll, ll>b) {
	return a.first > b.first;
}
pair<ll, ll>x[maxn];

ll dp[2][8000];
int main() {
	ios::sync_with_stdio(0);
	ll n, k;
	cin >> n >> k;
	//int tmp = 0;
	memset(dp, 0x3f, sizeof dp);
	dp[0][0] = dp[1][0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> x[i].second;
	}
	for (int i = 1; i <= n; i++) {
		cin >> x[i].first;
	}
	sort(x + 1, x + 1 + n,cmp);
	for (int i = 1; i <= n; i++) {
		int kk = i & 1;
		for (int j = 5000; j > 0; j--) {
			dp[kk][j] = min(dp[kk^1][j - 1] + x[i].first * (j - 1) + x[i].second, dp[kk^1][j]);
		}
		
	}
	for (int i = 5000; i >= 0; i--) {
		if (k >= dp[n & 1][i]) {
			cout << i << " ";
			break;
		}
	}
	//cout << ans;

}

题解#Trade#

Trade