题目内容

P1802

大意:现有 n 个好友可以打,有 x 瓶药水,每个好友有 lose_iwin_iuse_i 三个参数,分别表述了打输能获得多少经验,打赢能获得多少经验,需要多少瓶药水才打赢(如果使用的药水更少则赢不了),求最大能获得的经验乘五的值

解题思路

第一遍做的时候,想到的状态定义是 f_{i,j} 表示前 i 个人消耗 j 瓶药水能达到的最大经验,观察发现这个定义满足无后效性和最优子结构,所以开始想方程式。很明显,当我们面临一个人的时候,有两种决策:打——不打,而如果当前药品不够打的话肯定不能打,这里我枚举了使用的药量,但是没必要,这个不开 long long 的代码取得了 90 分的好成绩

#include <cstdio>

const int maxn=1e3+5;
int n,x,lose[maxn],win[maxn],use[maxn],f[maxn][maxn];

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%d %d",&n,&x);
    for(int i=1;i<=n;i++)
        scanf("%d %d %d",lose+i,win+i,use+i);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=x;j++)
        {
            for(int k=0;k<use[i];k++)
                f[i][j]=max(f[i][j],f[i-1][j-k]+lose[i]);
            if(j>=use[i])
                f[i][j]=max(f[i][j],f[i-1][j-use[i]]+win[i]);
        }
    printf("%d\n",f[n][x]*5);
    return 0;
}

然后仔细想想,发现其实这个可以进行优化,由于如果当前药量打不过的时候放多少药都没用,所以可以索性不放药,得到的答案也是正确的,同时,其实当药够打的时候,也是要考虑打还是投降两种情况的,并且空间的第一维可以像 0-1 背包一样优化掉。经过修改后的转移方程和代码如下:

f_j=\begin{cases}
\max(f_j+lose_i,f_{j-use_i}+win_i)\quad(j\ge use_i)\
f_j+lose_i\quad(j<use_i)
\end{cases}

#include <cstdio>
typedef long long ll;

const int maxn=1e3+5;
ll n,x,lose[maxn],win[maxn],use[maxn],f[maxn];

inline ll max(ll a,ll b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%lld %lld",&n,&x);
    ll ans=0;
    for(int i=1;i<=n;i++)
        scanf("%lld %lld %lld",lose+i,win+i,use+i);
    for(int i=1;i<=n;i++)
        for(int j=x;j>=0;j--)
        {
            if(j<use[i])
                f[j]+=lose[i];
            else
                f[j]=max(f[j]+lose[i],f[j-use[i]]+win[i]);
            ans=max(ans,f[j]);
        }
    printf("%lld\n",ans*5);
    return 0;
}
最后修改日期:2020年3月14日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。