AT_abc426_g [ABC426G] Range Knapsack Query 题解

· · 题解

AT_abc426_g [ABC426G] Range Knapsack Query 题解

解法

这道题求区间 01 背包的值，01 背包的值可以预处理，考虑分块。

设 f_{i,j} 表示第 i 个块到正在枚举的物品，容量不超过 j 的 01 背包价值，g_{i,j} 表示第 i 个物品到现在正在枚举的物品，容量不超过 j 的价值。注意 g 数组每次只处理一个块内的值。查询就是将两个数组合并，即 f_{bel_i,j}+g_{i,v-j}。

代码

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=2e4+10,M=2e5+10,len=150;
int n,m;
int w[N],v[N];
int ans[M];
int f[140][510],g[N][510];//f[i][j]第i个块到目前这个物品，容量不超过j的最大价值
//g[i][j]表示第i个物品到目前这个物品，容量不超过j的最大价值
int L[140],R[140],id[N];
struct que
{
    int id,l,c;
    que(int id=0,int l=0,int c=0) : id(id),l(l),c(c) {}
};
vector<que> q[N];
void add(int a[][510],int l,int r,int id)//将新物品加入整块/散块中
{
    for(int i=l;i<=r;i++)
        for(int j=500;j>=w[id];j--)
            a[i][j]=max(a[i][j],a[i][j-w[id]]+v[id]);
}
int query(int x,int y,int v)
{
    int res=0;
    for(int i=0;i<=v;i++)
        res=max(res,f[x][i]+g[y][v-i]);
    return res;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        id[i]=(i-1)/len+1;
    for(int i=1;i<=id[n];i++)
        L[i]=(i-1)*len+1,R[i]=i*len;;
    R[id[n]]=n;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    cin>>m;
    for(int i=1,l,r,c;i<=m;i++)
    {
        cin>>l>>r>>c;
        q[r].emplace_back(que(i,l,c));
    }
    for(int i=1;i<=n;i++)
    {
        add(f,1,id[i]-1,i);
        add(g,L[id[i]],i,i);
        for(auto j:q[i])
            ans[j.id]=query(id[j.l],j.l,j.c);
    }
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<endl;
    return 0;
}