https://codeforces.com/contest/1132/problem/E

题意

题解1

  • 多重背包二进制拆分物品转换成01背包,用map来剪枝掉无用的状态
#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,bool>f,g;
ll a[10],W,s[1005],ans;
vector<ll>w; int main(){
cin>>W;
for(ll i=1;i<=8;i++){
cin>>a[i];
if(a[i]){
ans=max(ans,min(W/i,a[i])*i);
ll num=1;
while(a[i]>0){
w.push_back(min(num,a[i])*i);
a[i]-=min(num,a[i]);
num*=2;
}
}
}
sort(w.begin(),w.end());
reverse(w.begin(),w.end());
for(int i=w.size()-1;i>=0;i--)s[i]=s[i+1]+w[i];
f[0]=true;
for(int i=0;i<w.size();i++){
g.clear();
for(map<ll,bool>::iterator it=f.begin();it!=f.end();it++){
ll x=it->first;
g[x]=true;
if(x+w[i]<=W)g[x+w[i]]=true;
}
f.clear();
for(map<ll,bool>::iterator it=g.begin();it!=g.end();it++){
ll x=it->first;
if(x+s[i]<ans)continue;
f[x]=true;
ans=max(ans,x);
}
}
cout<<ans;
}

题解2

参考:https://blog.csdn.net/qq_37451344/article/details/88860699

  • 设1到8的最小公倍数为lcm,则将lcm/V[i]看成一整份,然后枚举0到lcm/V[i]作为第二维
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll lcm=840;
ll W,a[10],V[10],dp[10][10005],ans;
int main(){
cin>>W;
for(int i=0;i<8;i++){
cin>>a[i];
V[i]=i+1;
}
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for(int i=0;i<8;i++){
ll num=lcm/V[i];
ll end=min(num,a[i]);
for(int j=0;j<=lcm*8;j++){
if(dp[i][j]<0)continue;
for(int k=0;k<=end;k++){
if(j+k*V[i]<=lcm*8)dp[i+1][j+k*V[i]]=max(dp[i+1][j+k*V[i]],
dp[i][j]+(a[i]-k)/num);
}
}
}
for(int i=0;i<=lcm*8;i++){
if(i>W)break;
if(dp[8][i]<0)continue;
ans=max(ans,i+lcm*min(dp[8][i],(W-i)/lcm));
}
cout<<ans;
}
05-11 09:37
查看更多