Lutece 2181 攻略妹纸

题目链接:
https://acm.uestc.edu.cn/problem/gong-lue-mei-zhi/description

题目大意:攻略一个妹纸有要求,可以获得愉悦度,求最大愉悦度

分析:

这道题一开始看输入数据太多,仔细看后其实还好。

将h即(d-k)* x排序后,就可以保证前面选的一定是满足的。

然后这道题就可以看做,重量上限动态变化的01背包问题。

5000的范围,开二维显然会爆,所以压成一维。一维的01背包,是倒序计算的。

然后很不幸的WA1了,因为Note里写着所有数都在int范围内,一直没往超范围想。

仔细确认了一遍01背包的思路,觉得我写的没有任何问题。所以改longlong,stable_sort,数组大小之类的。

过了,才意识到是爆int了。

代码:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;

///////////////////////////
struct meizi
{
    long long v,w,h;
}meizis[10001];
bool cmp(const meizi &a,const meizi &b)
{
    return a.h<b.h;
}
long long n,m,k,x,y;
long long a,b,c,d;
long long dp[10001];
long long ans=0;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    memset(dp,0,sizeof(dp));
    cin>>n>>m>>k>>x>>y;
    for(long long i=0;i<n;++i)
    {
        cin>>a>>b>>c>>d;
        meizis[i].v=a;
        if(c - b > 0)
        {
            meizis[i].w = ( c - b ) * y;
        }
        else
        {
            meizis[i].w = 0;
        }
        if(d - k > 0)
        {
            meizis[i].h = ( d - k ) * x;
        }
        else
        {
            meizis[i].h = 0;
        }
    }
    stable_sort(meizis,meizis+n,cmp);
    for(long long i=0;i<n;++i)
    {
        for(long long j = m-meizis[i].h;j>=meizis[i].w;--j)
        {
            dp[j]=max(dp[j],dp[j-meizis[i].w]+meizis[i].v);
            ans=max(ans,dp[j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注