[ACNOI2022]物品

题目

题目背景
当你感到疑惑时，不妨向神明祈祷；神可以回答一切问题。

$\mathsf{OneInDark}$：“卷爷为什么这么卷啊？”
$\mathsf{OUYE}$：“没有比这更质朴的快乐了。”

$\mathsf{DDG}$：“天天说别人二次元，有意思没有嘛。”
$\mathsf{OUYE}$：“这难道不令你感到舒适吗？”

最后是『神明三连击』：
$\mathsf{crashed}$：“哦，忘记给你说了……”
$\text{Tiw-Air-OAO}$：“你看到的只是表象……”
$\mathsf{OUYE}$：“本质是一样的！”

题目描述
重量为 $k(-m⩽k⩽m)$ 的物品有 $a_k$ 个，求重量和恰为 $L$ 的最多物品数，或报告无解。

数据范围与提示
$m⩽200$ 但 $|L|⩽10^{18}$ 以及 $a_k⩽10^{12}$ 。

思路

背包问题的最好优化方式是 $\text{balance}$ 。这个在子集和问题的论文中有说到。

简单来说，可以让背包重量始终在 $L$ 附近徘徊。因此我们可以略去很多无用信息。

与这道题也比较像，考虑我们需要怎样的调整。但套用那样的方法，得不到好的结果，因为权值与重量并不挂钩。

怎么让二者挂钩呢？性价比。所以我们的贪心初解按照性价比排序，然后这题就做完了！然而我就是想不到，悲夫。

完整地说一遍：先做初步转化，将重量为负数的物品先选上，则其权值变为 $-1$，即 “退回” 性价比为 $\frac{-1}{w}$ 。按照性价比排序，即先选择重量为 $1,2,\dots ,m$ 的物品，再 “退回” 重量为 $-m,-(m-1),\dots ,-1$ 的物品。

考虑最优解与其的差距。存在 $\text{balance}$ 方式，即总重量在 $[L-m,L+m]$ 内摇摆；若经过若干次操作后，总重量不变，该替换会使得性价比变低（否则贪心初解可以更优），因此是无意义的。

因此前缀和两两不同，即最多有 $2m$ 次调整。因此调整量不超过 $2m^2$，每个物品也只需考虑 $2m$ 以内的增减变化，拿出来做个部分背包即可。

时间复杂度 $\mathcal{O}(m^3)$，或者二进制分组 $\mathcal{O}(m^3\log m)$ 。

代码

#include <cstdio>
#include <algorithm> // Almighty XJX yyds!!
#include <cstring> // oracle: ZXY yydBUS!!!
#include <cctype> // rainybunny root of the evil.
#include <cstdint>
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
    
    int a = 0, c = getchar(), f = 1;
    for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
    for(; isdigit(c); c=getchar()) a = a*10+(c^48);
    return a*f;
}

const int MAXN = 300;
llong posi[MAXN+1], nega[MAXN+1];

const int MAXM = MAXN*(MAXN<<1);
const llong INF = (1ll<<60)-1;
llong dp[MAXM<<1|1];
void knapsack(const int& cnt, int weight, int value){
    
    if(cnt == 0) return;
    for(int j=0,w,v; true; ++j){
    
        if((cnt>>j) == 1){
    
            w = weight*(cnt^(1<<j))+weight;
            v = value*(cnt^(1<<j))+value;
        }
        else w = weight<<j, v = value<<j;
        if(w < 0) rep(i,-w,MAXM<<1)
            dp[i+w] = std::max(dp[i+w],dp[i]+v);
        else drep(i,MAXM<<1,w) // positive
            dp[i] = std::max(dp[i],dp[i-w]+v);
        if((cnt>>j) == 1) break;
    }
}

inline int trim(const llong& v){
    
    return v >= (MAXN<<1) ? (MAXN<<1) : int(v);
}
int main(){
    
    int n = readint();
    llong L; scanf("%lld",&L);
    drep(i,n,1) scanf("%lld",&nega[i]);
    llong ans; scanf("%lld",&ans);
    rep(i,1,n) scanf("%lld",&posi[i]);
    if(L < 0){
     // negate everything
        rep(i,1,n) std::swap(nega[i],posi[i]);
        L = -L;
    }
    rep(i,1,n) L += nega[i]*i;
    std::fill_n(dp,MAXM<<1|1,-INF);
    dp[MAXM] = 0; // known
    rep(i,1,n){
     // greedily use them
        llong cnt = std::min(L/i,posi[i]);
        L -= i*cnt, ans += cnt;
        knapsack(trim(cnt),-i,-1);
        knapsack(trim(posi[i]-cnt),i,1);
    }
    drep(i,n,1){
    
        llong cnt = std::min(L/i,nega[i]);
        L -= i*cnt, ans += nega[i]-cnt;
        knapsack(trim(cnt),-i,1);
        knapsack(trim(nega[i]-cnt),i,-1);
    }
    if(L < MAXM && ans+dp[L+MAXM] >= 0)
        printf("%lld\n",ans+dp[L+MAXM]);
    else puts("impossible");
    return 0;
}