题解 P6433 【「EZEC-1」出题】

pigstd · 2020-04-01 14:39:52 · 题解

update on 7.7:出题人谢罪，修改了一些锅，原来的数据太水了，希望管理员重新通过一下

此题是一道简单的背包dp。

先特判一遍，如果所有 x_{i} 的和小于等于 m ，那么就是一个贪心（因为父母会偷掉一道题），否则的话就不用管父母（因为不能全部出完数据，让父母偷掉一道没有出数据的题就可以了）。

然后用 dp_{i,j} 表示用 i 时间，使用 j 次翻倍后可以得到的最大毒瘤值。

对于每一对 a_{i} 和 x_{i} ，都有 dp_{i,j} = \max(dp_{i,j} , dp_{i-x_i , j} + a_i , dp_{i-x_i , j-1} + 2 \times a_i )

同时，老师可能没有用完，所以取 dp 数组中的最大值即可。

c++代码如下：

#include<bits/stdc++.h>
using namespace std;

int n,m,k,f[1005][105];
int a[1005],x[1005],sum,ans=0;

int cmp(int a,int b)
{
    return a>b;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&x[i]),sum+=x[i];
    if (sum<=m)//特判
    {
        int ans=0;
        sort(a+1,a+1+n,cmp);
        for (int i=1;i<=k;i++)
            ans+=a[i]*2;
        for (int i=k+1;i<n;i++)
            ans+=a[i];
        cout<<ans;
        return 0;
    }
    for (int e=1;e<=n;e++)
        for (int i=m;i>=x[e];i--)
        {
            for (int j=min(k,e);j>=1;j--)//注意，这里要倒叙枚举
                f[i][j]=max(f[i][j],max(f[i-x[e]][j]+a[e],f[i-x[e]][j-1]+a[e]*2)),ans=max(ans,f[i][j]);
            f[i][0]=max(f[i][0],f[i-x[e]][0]+a[e]);ans=max(ans,f[i][0]);
        }
    cout<<ans;
    return 0;
}