Codeforces 1154F (DP)

题意：有一个人去买铲子，他需要买正好k把。每把铲子有个标价，并且每把铲子最多只能被买一次。有m种优惠方案，每个优惠方案xi, yi是指如果这次恰好购买了xi把铲子，那么这次购买的铲子中最便宜的yi把将免费。问买k把铲子的最少花费。题目可以分多次购买铲子，只要购买的铲子总数是k把就可以。买过的铲子就不能再买了。

思路：显然，我们需要先对铲子的售价排个序，然后实际上购买的铲子就是最便宜的k把铲子，因为题目中要求购买恰好k把铲子，不能多，所以不存在去购买多余的铲子去凑优惠这种方案。那么现在的问题就变成了如何选择优惠策略，使得总花费最少。设dp[i]为购买前i把铲子的最小花费，初始值为sum[i]（sum[i]是排序之后的前缀和），意思是前i个铲子什么优惠都不用。我们枚举使用什么优惠去更新dp[i], dp[i] = min(dp[i - xj] + sum[i] - sum[i - xj +yj])。因为已经对花费排好序了，所以去除最小的yj个的花费是sum[i] - sum[i - xj + yj]。答案是dp[k]。

这个题感觉很水，不知道为什么难度是2300。。。可能是题意不是很好懂把。

代码：

#include <bits/stdc++.h>

#define LL long long

#define pii pair<int, int>

using namespace std;

const int maxn = 200010;

LL a[maxn], sum[maxn], dp[maxn];

pii b[maxn];

int main() {

	int n, m, k;

	scanf("%d%d%d", &n, &m, &k);

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

		scanf("%lld", &a[i]);

	}

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

		scanf("%d%d", &b[i].first, &b[i].second);

	}

	sort(a + 1, a + 1 + n);

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

		sum[i] = sum[i - 1] + a[i];

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

		dp[i] = sum[i];

		for (int j = 1; j <= m; j++) {

			if(i >= b[j].first) {

				dp[i] = min(dp[i], dp[i - b[j].first] + sum[i] - sum[i - b[j].first + b[j].second]);

			}

		}

	}

	printf("%lld\n", dp[k]);

}

巴特西

Codeforces 1154F (DP)

最新文章

热门文章