整体二分 HDU

题目大意

　　有n个物品，排成一个序列，每个物品有一个di表示取到i要走的距离，vi表示i的价值。

　　给m组询问[l,r] ,c,sum，问由[l,r]的di<=c的物品能否凑出sum的价值（每个物品只能用一次）

解法

　　首先说整体二分。

　　有m个对于区间的查询[Li,Ri]，考虑当前的二分区间[L,R]，对于所有包含于[L,R]的区间无非

　　是位于[L,mid]内，[mid+1,R]内和横跨mid三种情况。

　　前两种情况下递归求解，只需要对于第三种情况求解即可。

　　本题中，维护f(i,j)表示【用[i,mid]这些物品凑出j的价值所走的最长路】的最小值

　　　　　　而 g(i,j)表示【用[mid+1,i]这些物品凑出j的价值所走的最长路】的最小值

　　这样对于一个横跨mid的区间，只需要判断 min{ max{f(Li,j), g(Ri,sumi-j)} } 是否小于等于ci即可

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define N 20010

 #define M 100010

 #define INF 0x7fffffff

 using namespace std;

 struct qs

 {

     int l,r,c,sum,ansv,id;

 }a[M],a0[M],a1[M],b[M];

 int n,m,v[N],d[N],ansv[M],f[N][],g[N][];

 void dp(int l,int r)

 {

     int mid=(l+r)>>;

     for(int i=;i<=;i++) g[mid+][i]=f[mid][i]=INF;

     g[mid+][]=;

     g[mid+][v[mid+]]=d[mid+];

     for(int i=mid+;i<=r;i++)

     {

         for(int j=;j<=;j++) g[i][j]=g[i-][j];

         for(int j=v[i];j<=;j++)

             g[i][j] = min(g[i][j], max(g[i-][j-v[i]], d[i]));

     }

     f[mid][]=;

     f[mid][v[mid]]=d[mid];

     for(int i=mid-;i>=l;i--)

     {

         for(int j=;j<=;j++) f[i][j]=f[i+][j];

         for(int j=v[i];j<=;j++)

             f[i][j] = min(f[i][j], max(f[i+][j-v[i]], d[i]));

     }

 }

 void solve(int l,int r,int L,int R)

 {

     if(L>R) return;

     if(l==r)

     {

         for(int i=L;i<=R;i++)

         {

             if(d[l]<=a[i].c && a[i].sum==v[l]) a[i].ansv=;

             else a[i].ansv=;

         }

         return;

     }

     int mid=(l+r)>>;

     int tot0=,tot1=,tot=;

     for(int i=L;i<=R;i++)

     {

         if(a[i].r<=mid) a0[++tot0]=a[i];

         else if(a[i].l>mid) a1[++tot1]=a[i];

         else b[++tot]=a[i];

     }

     for(int i=;i<=tot0;i++) a[L+i-]=a0[i];

     for(int i=;i<=tot1;i++) a[L+tot0+i-]=a1[i];

     dp(l,r);

     for(int i=;i<=tot;i++)

     {

         int tmp=INF;

         for(int j=;j<=b[i].sum;j++)

         {

             int t=max(f[b[i].l][j], g[b[i].r][b[i].sum-j]);

             tmp=min(tmp,t);

         }

         if(tmp<=b[i].c) b[i].ansv=;

         else             b[i].ansv=;

     }

     for(int i=;i<=tot;i++) a[L+tot0+tot1+i-]=b[i];

     solve(l,mid,L,L+tot0-);

     solve(mid+,r,L+tot0,L+tot0+tot1-);

 }

 int main()

 {

 //    freopen("test.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++) scanf("%d",&v[i]);

         for(int i=;i<=n;i++) scanf("%d",&d[i]);

         for(int i=;i<=m;i++)

         {

             scanf("%d%d%d%d",&a[i].l,&a[i].r,&a[i].c,&a[i].sum);

             a[i].id=i;

         }

         solve(,n,,m);

         for(int i=;i<=m;i++) ansv[a[i].id]=a[i].ansv;

         for(int i=;i<=m;i++) putchar(ansv[i]? '':'');

         putchar('\n');

     }

 }

巴特西

整体二分 HDU - 5808

最新文章

热门文章