题解 P6240 【好吃的题目】

· · 题解

鉴于写博客的时候,没有简单的例题,于是就给你谷造了个这样的水题。

题意 : 区间01背包问题

更多信息可见 一些常用的数据结构维护手法

一些背包基础知识

这题的背包是最优化01背包。设F[i]表示容量为i时的最大总收益。

设背包大小为t,每次加入一个物品,复杂度是O(t)的。合并两个背包,复杂度是O(t^2)的。

假如已有两个背包F1[],F2[],查询合并后容量s所对应的收益,我们不必真的合并这两个背包。

计算 \max\limits_{i=0}^sF1[i]+F2[s-i] 即可。这样仅需O(t).

注意到背包实质上是\{\max,+\}卷积就很容易(bushi)理解了。

综上,由于本题t\leq 200,我们要避免O(t^2)的合并背包才行。

猫树分治·引入

考虑某种奇怪的静态序列问题,我们并不会做。

但是,如果所有询问的区间有交集,那么我们就能通过下列算法得出答案。

选取所有询问都包含的某个位置,分别向左向右预处理某些东西。

对于询问的回答,只需要在左端点取信息,在右端点取信息,再组合即可。这要求(答案/状态)能够合并。

然后我们套用猫树分治,就能够处理更一般的情况了。

此外,将分治树存下来,往往就能够做到强制在线。

考虑一堆询问区间和对应的状态区间[L,R]。

我们取状态区间的中点mid=\lfloor\frac{L+R}{2}\rfloor,从mid分别向左右预处理某些信息。

遍历所有询问,如果跨过(mid,mid+1),则合并左右端点信息来回答。

如果在[L,mid]中,则下放到左儿子。

如果在[mid+1,R]中,则下放到右儿子。

继续分治。

(不难发现其实就是序列上的点/边分治,所以上猫树的题目可能可以上点/边分树)

本题题解

考虑猫树分治,我们得到左右两侧背包,只需要合并求一个值,那么就可以使用上文O(t)的方法。

这些背包需要分治并建立,需要O(nt)的空间和O(nt\log n)的时间。

总复杂度O(nt\log n+qt),实现细节请查看代码。

#include<algorithm>
#include<cstdio>
#define MaxM 200500
#define MaxN 40500
using namespace std;
inline int read(){
  register int X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int n,m,h[MaxN],w[MaxN],f[MaxN][205];
struct Data
{int l,r,t;}b[MaxM];
int p[MaxM],s[MaxM],ans[MaxM],tn;
void solve(int l,int r,int tl,int tr)
{
  if (tl>tr)return ;
  int mid=(l+r)>>1,tmid=tl-1;
  for (int j=0;j<=200;j++)f[mid][j]=0;
  for (int i=mid+1;i<=r;i++){
    for (int j=0;j<h[i];j++)f[i][j]=f[i-1][j];
    for (int j=h[i];j<=200;j++)
      f[i][j]=max(f[i-1][j],f[i-1][j-h[i]]+w[i]);
  }
  for (int j=h[mid];j<=200;j++)f[mid][j]=w[mid];
  for (int i=mid-1;i>=l;i--){
    for (int j=0;j<h[i];j++)f[i][j]=f[i+1][j];
    for (int j=h[i];j<=200;j++)
      f[i][j]=max(f[i+1][j],f[i+1][j-h[i]]+w[i]);
  }tn=0;
  for (int i=tl,u;i<=tr;i++){
    u=p[i];
    if (b[u].r<=mid)p[++tmid]=u;
    else if (mid<b[u].l)s[++tn]=u;
    else {
      int ret=0;
      for (int i=0;i<=b[u].t;i++)
        ret=max(ret,f[b[u].l][i]+f[b[u].r][b[u].t-i]);
      ans[u]=ret;
    }
  }for (int i=1;i<=tn;i++)p[tmid+i]=s[i];
  tr=tn+tmid;
  solve(l,mid,tl,tmid);
  solve(mid+1,r,tmid+1,tr);
}
int main()
{
  n=read();m=read();
  for (int i=1;i<=n;i++)h[i]=read();
  for (int i=1;i<=n;i++)w[i]=read();
  for (int i=1;i<=m;i++){
    b[i].l=read();b[i].r=read();
    b[i].t=read();
    if (b[i].l==b[i].r){
      if (b[i].t>=h[b[i].l])ans[i]=w[b[i].l];
    }else p[++tn]=i;
  }solve(1,n,1,tn);
  for (int i=1;i<=m;i++)
    printf("%d\n",ans[i]);
  return 0;
}