标签：背包 int memset 矿石 融合 3005 sizeof
- 无论怎么融合，合法矿石的质量至多只有3000种，可以通过一遍完全背包预处理得到，然后再跑一遍完全背包就好了
- 还记得完全背包吗？就是把01背包正过来跑一遍就好了
- 想不出来的时候，不妨暂时放下，回头再看，或许能有新的发现
- 没有金辉石的矿石没有价值
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int v[15],f[3005],g[3005];
int a[3005],b[3005],w[3005];
int val(int a,int b)
{
if(a==0)
{
return 0;
}
for(int i=1;i<=10;i++)
{
if(a*10<=i*b)
{
return v[i];
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
for(int i=1;i<=10;i++)
{
cin>>v[i];
}
int n,m;
cin>>n>>m;
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
for(int j=a[i];j<=m;j++)
{
f[j]=max(f[j],f[j-a[i]]+b[i]);
}
}
for(int i=1;i<=m;i++)
{
w[i]=val(f[i],i)*i;
}
int ans=0;
for(int i=1;i<=m;i++)
{
for(int j=i;j<=m;j++)
{
g[j]=max(g[j],g[j-i]+w[i]);
}
}
for(int i=1;i<=m;i++)
{
ans=max(ans,g[i]);
}
cout<<ans<<endl;
}
return 0;
}
标签：背包,
int,
memset,
矿石,
融合,
3005,
sizeof
From： https://www.cnblogs.com/watersail/p/18374741