题目内容
大意:现有 n 个好友可以打,有 x 瓶药水,每个好友有 lose_i,win_i,use_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;
}
留言