mcfx's blog

题解、Writeup、游记和碎碎念

BZOJ 3163: [Heoi2013]Eden的新背包问题

“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。” 失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。记忆中，她总是喜欢给 Eden 出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 n 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱 m 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？

Sample Output

Solution

多重背包+分治背包。

递归处理 $[l,r)$ ，每次加入左半部分的点，处理右边，再加入右边，处理左边。

时间复杂度 $O(n^2\log^2n+q)$ 。

Code

#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d)

struct _toy
{
    int a,b,c;
}toy[1000];

struct _qr
{
    int w,ans,ne;
}qr[300001];

int p[1000],n,q,f[11][1001];

inline void merge(int *s,int a,int b)
{
    for(int i=1000;i>=a;i--)
        repr(s[i],max(s[i-1],s[i-a]+b));
}

void solve(int l,int r,int d)
{
    if(l+1==r)
    {
        for(int i=p[l];i;i=qr[i].ne)
            qr[i].ans=f[d][qr[i].w];
    }
    else
    {
        int p=(l+r)>>1;
        memcpy(f[d+1],f[d],sizeof(f[d]));
        for(int i=l;i<p;i++)
        {
            int t=toy[i].c;
            for(int j=1;j<t;t-=j,j<<=1)
                merge(f[d+1],toy[i].a*j,toy[i].b*j);
            merge(f[d+1],toy[i].a*t,toy[i].b*t);
        }
        solve(p,r,d+1);
        memcpy(f[d+1],f[d],sizeof(f[d]));
        for(int i=p;i<r;i++)
        {
            int t=toy[i].c;
            for(int j=1;j<t;t-=j,j<<=1)
                merge(f[d+1],toy[i].a*j,toy[i].b*j);
            merge(f[d+1],toy[i].a*t,toy[i].b*t);
        }
        solve(l,p,d+1);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d%d",&toy[i].a,&toy[i].b,&toy[i].c);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int x;
        scanf("%d%d",&x,&qr[i].w);
        qr[i].ne=p[x];
        p[x]=i;
    }
    solve(0,n,0);
    for(int i=1;i<=q;i++)
        printf("%d\n",qr[i].ans);
}

日期： 2016-11-15
标签： BZOJ 背包dp
这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/74/ 查看。

mcfx's blog

BZOJ 3163: [Heoi2013]Eden的新背包问题

Input

Output

Sample Input

Sample Output

Solution

Code