题解:这题我们需要考虑两个因素 ,既要有钱,也需要有人品,但是呢,还想花最少得时间泡到最多的女生,那么这题我们就要用到以往的二维dp数组,但是真的是二维的吗?不,因为要考虑女生的数量以及时间,真正应该是三维的,因此,我们可以得到状态转移方程式,
当数量可以增加时,数量和时间都要相应增加,但是当人数不变时,只需要考虑最小时间,吟哦写出dp方程式
if(dp[j][k][0]<dp[j-rmb[i]][k-rp[i]][0]+1)
{
dp[j][k][0]=dp[j-rmb[i]][k-rp[i]][0]+1;
dp[j][k][1]=dp[j-rmb[i]][k-rp[i]][1]+t[i];
}
if(dp[j][k][0]==dp[j-rmb[i]][k-rp[i]][0]+1)
dp[j][k][1]=min(dp[j][k][1],dp[j-rmb[i]][k-rp[i]][1]+t[i]);
AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,r;
int rmb[105],rp[105],t[105];
int dp[105][105][2];
int rmax=0,tmax=0x3f3f3f3f;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&rmb[i],&rp[i],&t[i]);
}
scanf("%d%d",&m,&r);
for(int i=1;i<=n;i++)
{
for(int j=m;j>=rmb[i];j--)
{
for(int k=r;k>=rp[i];k--)
{
if(dp[j][k][0]<dp[j-rmb[i]][k-rp[i]][0]+1)
{
dp[j][k][0]=dp[j-rmb[i]][k-rp[i]][0]+1;
dp[j][k][1]=dp[j-rmb[i]][k-rp[i]][1]+t[i];
}
if(dp[j][k][0]==dp[j-rmb[i]][k-rp[i]][0]+1)
dp[j][k][1]=min(dp[j][k][1],dp[j-rmb[i]][k-rp[i]][1]+t[i]);
}
}
}
printf("%d",dp[m][r][1]);
return 0;
}