[題目連結]
有很多小牛,每隻有一個幽默度和智商,要選出一些小牛,智商加幽默度總和最大,其中智商總和和幽默度總和都不能是負數。
思路:
變種的01背包,可以把幽默度看成體積,智商看成價值,那麼就轉換成求體積和價值都為正值的最大值的01背包了。(一看就有點01背包的感覺,可是還是菜啊~~)
代碼:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=;
const int N=;
const int Max_n=+;
int n;
int s[N],f[N];
int dp[Max_n];
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d",&s[i],&f[i]);
}
int flag=;
for(int i=;i<Max_n;i++)dp[i]=-inf;
dp[flag]=;
for(int i=;i<n;i++){
if(s[i]<){
for(int j=;j<Max_n+s[i];j++)
dp[j]=max(dp[j],dp[j-s[i]]+f[i]);
}
else {
for(int j=Max_n-;j>=s[i];j--)
dp[j]=max(dp[j],dp[j-s[i]]+f[i]);
}
}
int Max=;
for(int i=flag;i<Max_n;i++){
if(dp[i]>=)Max=max(Max,dp[i]+i-flag);
}
printf("%d\n",Max);
return ;
}