Codeforces Round #610 B2. K for the Price of One (Hard Version)

刺骨的言语ヽ痛彻心扉 2023-06-25 08:12 9阅读 0赞

题目内容就不放上来了。

思路：

分析一组数据

5 6 2
    2 4 3 5 7

对其排序以后为：2 3 4 5 7

一个很明显的性质，要想买的最多，肯定是买前面的。

若有一个数2，那么只有一种方式。

如果有两个数 2 3，那么此时可以先买2，后买3. 或者直接买3（因为现在k=2，买了3以后，可以直接获得2）

设dp\[i\]表示前i个物品花费的最小钱数。那么应该有下面的递推式。

dp\[i\]=min(dp\[i-1\]+a\[i\],dp\[i-k\]+a\[i\]) .意思是，前i个的最小量，要么从前i-1个转移过来，要么从i-k个转移过来。

为何想到这样？因为从第一个数开始逐一分析，发现它是有最优子结构的。

这题的命题思路应该是模仿了求最长子序列和背包。

代码如下：

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=2e5+7;
    int a[maxn];
    int dp[maxn];
    int main()
    {
        #ifndef ONLINE_JUDGE
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
        #endif
        int T;
        scanf("%d",&T);
        int n,p,k;
        while(T--)
        {
            cin>>n>>p>>k;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            //memset(dp,0,sizeof(dp));
            sort(a+1,a+n+1);
            int ans=0;
            dp[0]=0;
            for(int i=1;i<=n;i++)
            {
                dp[i]=dp[i-1]+a[i];
                if(i>=k)
                {
                    dp[i]=min(dp[i],dp[i-k]+a[i]);
                }
                if(dp[i]<=p){
                    ans=max(ans,i);
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }