题解 P2623 【物品选取】
啊哈，题目在这里
题意很明显嘛
三个背包
不知道大佬们说的函数背包是什么东东，~~虽然的却很形象~ ~
甲：
当时只是觉得甲可以根据他给的式子直接来写对应体积的价值然后来跑
乙：
对于每个个数处理一手，然后依旧跑
丙：
完全背包
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1000010
using namespace std;
int re() {
int p=0; char i=getchar();
while(i<'0'||i>'9') i=getchar();
while(i>='0'&&i<='9') p=p*10+i-'0',i=getchar();
return p;
}
int n,m,cnt;
int w[N],v[N],r[N];
int f[N];
int main()
{
n=re(); m=re();
if(n==0||m==0) {
cout<<0<<endl;
return 0;
}
for(int i=1;i<=n;i++)
{
int op,x,y,z;
op=re();x=re();y=re();
if(op==1)
{
for(int j=1;j<=m;j++)
{
if(x*j-y<=0) continue;
v[++cnt]=j;
w[cnt]=j*(j*x-y);
r[cnt]=1;
}
}
if(op==2)
{
int k=1; z=re();
while(z>0)
{
int mi=min(k,z);
w[++cnt]=mi*x;
v[cnt]=mi*y;
r[cnt]=1;
z-=k; k<<=1;
}
}
if(op==3)
{
w[++cnt]=x;
v[cnt]=y;
r[cnt]=0;
}
}
for(int i=1;i<=cnt;i++)
{
if(r[i]==0)
{
for(int j=v[i];j<=m;j++) f[j]=max(f[j-v[i]]+w[i],f[j]);
}
else {
for(int j=m;j>=v[i];j--) f[j]=max(f[j-v[i]]+w[i],f[j]);
}
}
cout<<f[m]<<endl;
return 0;
}