【动态规划】Codeforce 1282B2 K for the Price of One (Hard Version) CodeForce

保研之后的休闲时光

一、题目大意题目的大致意思如下，有一家商店举办活动，可以用一个商品的价钱购买走K件商品，需要付出的价钱是这K件商品的最大值。题目给定你具有的金钱p，商品数n和商品价格数组a，要你求解最多能买多少件商品，规定每一件商品仅能购买一次。
二、题目思路以及AC代码这题是上一道题 Codeforce 1282 B1 的一个困难版本，说是困难，其实就是用时间把暴力的方法给卡了… 我做题就很循规蹈矩，上一道题正好是暴力解决的。
好，下面来说一下这道题的思路，其实会了暴力的方法，这道题无非就是用动态规划去去除一些暴力方法的重复运算，正好两道题对比可以看出时间效率上的显著提高，那么如何进行动态规划呢？
考虑我们要购买第i件商品时的所有可能情况。为了方便说明，这里借用我定义的几个数组。
rest数组：rest[i]，表示当前还剩多少钱
dp数组：dp[i]，表示截至看到第i件商品，用所有的钱p最多可以购买多少件。
a数组：a[i]，表示第i件商品的价钱

下面就是所有可能遇到的情况，当遇到第i件商品的时候，我们有两种选择：
① 用金钱a[i]购买这件商品，并且同时取走相邻小于a[i]的k件商品
② 用金钱a[i]购买这件商品，且仅取走这件商品
这里要注意，题目要求只有这两种情况，不存在你购买商品后拿走小于k件商品。
所以当你遇到第i件商品的时候，只需要取上述两种结果较大的一个即可。注意，不可以中途跳出，我说的中途跳出的意思，是不要以为你中途判断的时候，发现当前的钱已经不足以购买，就直接break，因为你当前的钱仅仅是针对这种选择链的，并不是全局。
之后dp的递推公式也就很好得到了，详细见代码吧，因为这个递推公式有些条件不太好打出来，这里我可以先口述一下。对于dp[i]和rest[i]的确定，简单来说，只要求dp[i-k] + k和dp[i-1] + 1的最大值即可，但要考虑几个问题：
① dp[i-k]是否存在，因为在你遍历前几个的时候，i是小于k的
② 注意比较钱是否够的时候，要比较两个，分别是rest[i-k]和rest[i-1]，对应不同的选择
嗯，大致就这么多问题，讲解应该也比较细致，下面给出AC代码，这个代码是62ms，可以看出比之前的2000多ms可是快了不少。
这里再提醒一个问题，这里的数组均不需要初始化，如果初始化的话会造成TLE！具体原因自己琢磨去吧，篇幅太长啦!!!
AC代码：

#include #include #define MAXN 200010 #define INF 10000000000 using namespace std; // 商品价格数组 int a[MAXN]; // dp为动归数组，rest为对应的剩余金钱 int dp[MAXN]; int rest[MAXN]; int main() {int T; scanf("%d", &T); while (T--) { // init(); int n, p, k; scanf("%d %d %d", &n, &p, &k); for (int i=1; i<=n; i++) { scanf("%d", &a[i]); }sort(a+1, a+n+1); // 截至第0件商品，用金钱p最多可以购买0件 dp[0] = 0; rest[0] = p; int i; for (i=1; i<=n; i++) { if (i= a[i]) { dp[i] = dp[i-1] + 1; rest[i] = rest[i-1] - a[i]; } else { dp[i] = dp[i-1]; rest[i] = rest[i-1]; } } else { if (rest[i-1] >= a[i] && rest[i-k] >= a[i]) { int num_1 = dp[i-1] + 1; int num_k = dp[i-k] + k; if (num_1 > num_k) { dp[i] = num_1; rest[i] = rest[i-1] - a[i]; } else { dp[i] = num_k; rest[i] = rest[i-k] - a[i]; } continue; } if (rest[i-1] >= a[i] && rest[i-k] < a[i]) { dp[i] = dp[i-1] + 1; rest[i] = rest[i-1] - a[i]; continue; } if (rest[i-1] < a[i] && rest[i-k] >= a[i]) { dp[i] = dp[i-k] + k; rest[i] = rest[i-k] - a[i]; continue; } dp[i] = dp[i-1]; rest[i] = rest[i-1]; } }cout << dp[n] << endl; }return 0; }

【【动态规划】Codeforce 1282B2 K for the Price of One (Hard Version)】如果有问题，欢迎大家指正！！！