题解：P8392 [BalticOI 2022 Day1] Uplifting Excursion

zhm080507 · 2024-09-30 20:28:53 · 题解

题意描述

要在权值为 [-m,m] 中选若干个物品，使它们的权值之和为 L，并使它们的个数之和尽可能大。

算法分析

• 首先我们可以发现选取物品的最优一定是小的多选，那我们可以先将全部都选进来，然后再从大到小删除；

  最后的结果 sum 一定是属于 [L-m,L+m] 的。

if(sum>L){//如果大了，从m开始删 
        for(int i=2*m;i>m;i--){
            tmp=sum-L;
            b[i]-=min(tmp/(i-m),a[i]);//注意上限 
            sum-=(i-m)*(a[i]-b[i]);
        }
    }else{//如果小了，从-m删 
        for(int i=0;i<m;i++){
            tmp=L-sum;
            b[i]-=min(tmp/(m-i),a[i]);
            sum-=(i-m)*(a[i]-b[i]);
        }
    }
    //a为总数，b为用了的个数 

• 现在我们的目标就变成了在当前基础上进行调整，使最后的合并结果变为 L。

  我们容易发现对于每一次跳动的最大限度是 m，所以一定存在策略能使 sum 维持在 [L-m,L+m] 中； 而一个当前的 sum，在第二次出现时经过调整，结果一定不优；

  由此，对于每个物品，因为其每次使用造成的影响至少为 1，所以至多有 m 个变化是有效的，所以得出 sum 的有效值域为 [L-m^2,L+m^2]，所以在这里面进行多重背包时，物品个数最多为 m^2 个。

  siz=m*m*2;
  memset(f,-0x3f,sizeof(f));
  /*
  接下来在(L-m^2,L+m^2)的值域中跑多重背包 
  对于物品个数：
      因为对于一个在(L-m^2,L+m^2)中的值，我们最多只能到达一次， 
  因为多次变化后答案更劣。而每一个物品加入或删除至少变化一，所
  以对于每种物品最多考虑m^2个 
  */ 
  tmp=m*m-L+sum;f[tmp]=0;//背包边界 
  for(int i=0;i<=2*m;i++)
      f[tmp]+=b[i];//初始化，当前情况用了多少 
  for(int i=0;i<=2*m;i++){
      if(i==m) continue;//价值为0的物品显然全选 
      if(b[i])//如果有用了的，考虑删除 
          add(-(i-m),-1,min(b[i],(ll)siz)) ;
      if(a[i]-b[i])//如果有没用的，考虑添加 
          add(i-m,1,min(a[i]-b[i],(ll)siz)) ;
  }

  另外，对于多重背包因为复杂度为 O(m*(m^2)^2)=O(m^5)，所以用二进制优化为O(m^3log(m^2))。

  void add(ll w,ll v,int c){
  //w表示当前操作一次对sum的影响，v表示对结果的影响，c表示物品个数
  if(w>0){
      for(int s=1;c>0;c-=s,s<<=1){
      int k=min(s,c);//二进制优化多重背包 
      for(int i=siz;i>=k*w;i--)
          f[i]=max(f[i],f[i-k*w]+k*v);
      //倒序跑01背包
    }
  }else{
      for(int s=1;c>0;c-=s,s<<=1) {
          int k=min(s,c);
      for (int i=0; i-k*w<=siz;++i)
          f[i]=max(f[i],f[i-k*w]+k * v);
      }
  }
  }

• 特别的，对于超过值域范围的 L 需要特判掉。

  cin>>m>>L;
  for(int i=0;i<=2*m;i++){
      cin>>a[i];b[i]=a[i];
      //a为总数，b为用了的个数 
      if(i<m) dm+=a[i]*(i-m);
      else um+=a[i]*(i-m);
  }//记录上下边界 
  if(L<dm||L>um){
      printf("impossible\n");
      return 0;
  }//如果超出，直接结束 

完整代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int M=310;
ll m,L,dm,um,tmp,sum;
ll a[M*2], b[M*2];
ll siz;
ll f[M*M*2];

void add(ll w,ll v,int c){
    //w表示当前操作一次对sum的影响，v表示对结果的影响，c表示物品个数
    if(w>0){
        for(int s=1;c>0;c-=s,s<<=1){
        int k=min(s,c);//二进制优化多重背包 
        for(int i=siz;i>=k*w;i--)
            f[i]=max(f[i],f[i-k*w]+k*v);
        //倒序跑01背包
    }
    }else{
        for(int s=1;c>0;c-=s,s<<=1) {
            int k=min(s,c);
        for (int i=0; i-k*w<=siz;++i)
            f[i]=max(f[i],f[i-k*w]+k * v);
        }
    }
}

int main(){
//  freopen("greedy.in", "r", stdin);
//  freopen("greedy.out", "w", stdout);
    cin>>m>>L;
    for(int i=0;i<=2*m;i++){
        cin>>a[i];b[i]=a[i];
        //a为总数，b为用了的个数 
        if(i<m) dm+=a[i]*(i-m);
        else um+=a[i]*(i-m);
    }//记录上下边界 
    if(L<dm||L>um){
        printf("impossible\n");
        return 0;
    }//如果超出，直接结束 
    sum=dm+um;
    if(sum>L){//如果大了，从m开始删 
        for(int i=2*m;i>m;i--){
            tmp=sum-L;
            b[i]-=min(tmp/(i-m),a[i]);//注意上限 
            sum-=(i-m)*(a[i]-b[i]);
        }
    }else{//如果小了，从-m删 
        for(int i=0;i<m;i++){
            tmp=L-sum;
            b[i]-=min(tmp/(m-i),a[i]);
            sum-=(i-m)*(a[i]-b[i]);
        }
    }
    siz=m*m*2;
    memset(f,-0x3f,sizeof(f));
    /*
    接下来在(L-m^2,L+m^2)的值域中跑多重背包 
    对于物品个数：
        因为对于一个在(L-m^2,L+m^2)中的值，我们最多只能到达一次， 
    因为多次变化后答案更劣。而每一个物品加入或删除至少变化一，所
    以对于每种物品最多考虑m^2个 
    */ 
    tmp=m*m-L+sum;f[tmp]=0;//背包边界 
    for(int i=0;i<=2*m;i++)
        f[tmp]+=b[i];//初始化，当前情况用了多少 
    for(int i=0;i<=2*m;i++){
        if(i==m) continue;//价值为0的物品显然全选 
        if(b[i])//如果有用了的，考虑删除 
            add(-(i-m),-1,min(b[i],(ll)siz)) ;
        if(a[i]-b[i])//如果有没用的，考虑添加 
            add(i-m,1,min(a[i]-b[i],(ll)siz)) ;
    } 
    if(f[m*m]<0) cout<<"impossible"<<endl;
    else cout<<f[m*m]<<endl;
    return 0;
}