题目

传送门

思路

如果暴力背包必然会T，

但是机房巨佬JZM好像直接用DP过了

我们考虑，如果只有1和2两种重量

我们可以用一个\(log\)来处理出答案

先用重量为2暴力填入背包，

我们考虑将价值最小的一个重量为2的推出背包意味着价值最大的两个重量为1的物品价值之和大于重量为2的最小价值

这很显然是一个单调的函数

用二分和前缀和可以很轻松地实现\(log\)的求解

最后我们枚举一下重量为3的个数即可

代码

#include
#include
#include
using namespace std;
int n,m;
long long ans;
long long w[4][300005],s[4][300005],len[4];
bool cmp(const int &a,const int &b)
{
return a>b;
}
long long solve(long long m)
{
int l=1,r=m/2,mid=m/2;
while(l+1 {
mid=(l+r)>>1;
if(w[2][mid]<=w[1][(m-mid*2)+1]+w[1][(m-mid*2)+2])
r=mid;
else
l=mid;
}
if(m-(mid+1)*2>=0)
mid++;
while(w[2][mid]<=w[1][(m-mid*2)+1]+w[1][(m-mid*2)+2]&&mid-1>=0)
mid--;
return s[2][mid]+s[1][(m-mid*2)];
}
int main()
{
cin>>n>>m;
for(int i=1,wei,val;i<=n;i++)
{
cin>>wei>>val;
w[wei][++len[wei]]=val;
}
len[1]=len[2]=len[3]=300000;
for(int i=1;i<=3;i++)
sort(w[i]+1,w[i]+len[i]+1,cmp);
for(int i=1;i<=3;i++)
for(int j=1;j<=len[i];j++)
s[i][j]=s[i][j-1]+w[i][j];
for(int i=0;i<=len[3]&&3*i<=m;i++)
ans=max(ans,s[3][i]+solve(m-3*i));
cout< return 0;
}


习题：Selling Souvenirs（二分）