P8392 BalticOI 2022 Day1 Uplifting Excursion

贪心加动规，好题，这两个甚至完全相反的东西可以融进一道题……

思路

物品较少，贡献较小，体积较小，但总体积巨大。

直接上 \(dp\) 容易把心态搞炸。

我们可以先考虑贪心，使贡献最多还剩 \(m\)。然后考虑背包填满剩下的体积，且 \(i\) 和 \(-i\) （这里的 \(-i\) 是撤销）的物品是不会重复出现在背包中的，如果重复出现了那么肯定不优，所以最多再加入 \(2m\) 个数，背包值域开 \([-m^2,m^2]\)。

为什么这里的贪心加 \(dp\)​ 是正确的呢？

• 由于贡献相同，贪心选体积最小的物品肯定可以选择最多。

• 我们在贪心之后进行了 \(dp\) 调整，这个调整是可以反悔减少物品的，也就是我们的 \(f[l]\) 会在体积满足 \(l\)​ 的情况下尽可能多的增加，尽可能少的减少物品，这也是和普通背包的区别。

那么最后我们得出的答案一方面保证了体积肯定符合规定，一方面保证了贪心和动规选出的或是减少的数都是最多或最少的。

实现

我们在一开始可以先加上所有负数状态，后面的正数状态加入时就相当于也选择了负数。

    scanf("%lld%lld",&n,&l);
    for(int i=n;i;i--) scanf("%lld",&a[i]),l+=a[i]*i,ans+=a[i];
    int t;
    scanf("%lld",&t);ans+=t;
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    if(l<0){printf("impossible");return 0;}
    for(int i=1;i<=n;i++)
    {
        if(b[i]*i<=l) l-=b[i]*i,ans+=(b1[i]=b[i]);
        else {b1[i]=l/i;ans+=b1[i];l-=b1[i]*i;break;}
    }
    for(int i=n;i;i--)
    {
        if(a[i]*i<=l) l-=a[i]*i,ans-=(a1[i]=a[i]);
        else {a1[i]=l/i;ans-=a1[i];l-=a1[i]*i;break;}
    }

\(a1,b1\) 记录了选择了多少。

背包可以写成函数的形式并使用二进制优化。

void ins(ll s,ll v,ll w)//s ->数量，v ->体积，w ->贡献
{
    s=min(s,n*2+1);
    if(v>0)
    {
        int c=1;
        for(;c+c<s;c<<=1,v<<=1,w<<=1);
        while(1)
        {
            for(int i=k-v;i>=0;i--) f[i+v]=max(f[i+v],f[i]+w);
            s-=c;
            if(c==1) break;
            c>>=1,v>>=1,w>>=1;
        }
        if(s>0)
        {
            v*=s,w*=s;
            for(int i=k-v;i>=0;i--) f[i+v]=max(f[i+v],f[i]+w);
        }
    }
    else
    {
        v=-v;
        int c=1;
        for(;c+c<s;c<<=1,v<<=1,w<<=1);
        while(1)
        {
            for(int i=v;i<=k;i++) f[i-v]=max(f[i-v],f[i]+w);
            s-=c;
            if(c==1) break;
            c>>=1,v>>=1,w>>=1;
        }
        if(s>0)
        {
            v*=s,w*=s;
            for(int i=v;i<=k;i++) f[i-v]=max(f[i-v],f[i]+w);
        }
    }
}

CODE

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

#define ll long long
#define int long long

const int maxn=505;

ll l,n,m,k,ans;
ll a[maxn],b[maxn],a1[maxn],b1[maxn];
ll f[maxn*maxn*2];

void ins(ll s,ll v,ll w)
{
    s=min(s,n*2+1);
    if(v>0)
    {
        int c=1;
        for(;c+c<s;c<<=1,v<<=1,w<<=1);
        while(1)
        {
            for(int i=k-v;i>=0;i--) f[i+v]=max(f[i+v],f[i]+w);
            s-=c;
            if(c==1) break;
            c>>=1,v>>=1,w>>=1;
        }
        if(s>0)
        {
            v*=s,w*=s;
            for(int i=k-v;i>=0;i--) f[i+v]=max(f[i+v],f[i]+w);
        }
    }
    else
    {
        v=-v;
        int c=1;
        for(;c+c<s;c<<=1,v<<=1,w<<=1);
        while(1)
        {
            for(int i=v;i<=k;i++) f[i-v]=max(f[i-v],f[i]+w);
            s-=c;
            if(c==1) break;
            c>>=1,v>>=1,w>>=1;
        }
        if(s>0)
        {
            v*=s,w*=s;
            for(int i=v;i<=k;i++) f[i-v]=max(f[i-v],f[i]+w);
        }
    }
}

signed main()
{
    scanf("%lld%lld",&n,&l);
    for(int i=n;i;i--) scanf("%lld",&a[i]),l+=a[i]*i,ans+=a[i];
    int t;
    scanf("%lld",&t);ans+=t;
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    if(l<0){printf("impossible");return 0;}
    for(int i=1;i<=n;i++)
    {
        if(b[i]*i<=l) l-=b[i]*i,ans+=(b1[i]=b[i]);
        else {b1[i]=l/i;ans+=b1[i];l-=b1[i]*i;break;}
    }
    for(int i=n;i;i--)
    {
        if(a[i]*i<=l) l-=a[i]*i,ans-=(a1[i]=a[i]);
        else {a1[i]=l/i;ans-=a1[i];l-=a1[i]*i;break;}
    }
    m=n*n,k=m*2;
    memset(f,0xcf,sizeof(f));
    f[m]=0;
    for(int i=1;i<=n;i++)
    {
        if(b1[i]) ins(b1[i],-i,-1);
        if(b[i]-b1[i]) ins(b[i]-b1[i],i,1);
        if(a1[i]) ins(a1[i],-i,1);
        if(a[i]-a1[i]) ins(a[i]-a1[i],i,-1);
    }
    if(l>m||f[m+l]<-m){printf("impossible");return 0;}
    else printf("%lld",ans+f[m+l]);
}

记得全开 long long。