整体二分 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即可

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 #define N 20010
 6 #define M 100010
 7 #define INF 0x7fffffff
 8 
 9 using namespace std;
10 
11 struct qs
12 {
13     int l,r,c,sum,ansv,id;
14 }a[M],a0[M],a1[M],b[M];
15 
16 int n,m,v[N],d[N],ansv[M],f[N][101],g[N][101];
17 
18 void dp(int l,int r)
19 {
20     int mid=(l+r)>>1;
21     for(int i=0;i<=100;i++) g[mid+1][i]=f[mid][i]=INF;
22     g[mid+1][0]=0;
23     g[mid+1][v[mid+1]]=d[mid+1];
24     for(int i=mid+2;i<=r;i++)
25     {
26         for(int j=0;j<=100;j++) g[i][j]=g[i-1][j];
27         for(int j=v[i];j<=100;j++)
28             g[i][j] = min(g[i][j], max(g[i-1][j-v[i]], d[i]));
29     }
30     f[mid][0]=0;
31     f[mid][v[mid]]=d[mid];
32     for(int i=mid-1;i>=l;i--)
33     {
34         for(int j=0;j<=100;j++) f[i][j]=f[i+1][j];
35         for(int j=v[i];j<=100;j++)
36             f[i][j] = min(f[i][j], max(f[i+1][j-v[i]], d[i]));
37     }
38 }
39 
40 void solve(int l,int r,int L,int R)
41 {
42     if(L>R) return;
43     if(l==r)
44     {
45         for(int i=L;i<=R;i++)
46         {
47             if(d[l]<=a[i].c && a[i].sum==v[l]) a[i].ansv=1;
48             else a[i].ansv=0;
49         }
50         return;
51     }
52     int mid=(l+r)>>1;
53     int tot0=0,tot1=0,tot=0;
54     for(int i=L;i<=R;i++)
55     {
56         if(a[i].r<=mid) a0[++tot0]=a[i];
57         else if(a[i].l>mid) a1[++tot1]=a[i];
58         else b[++tot]=a[i];
59     }
60     for(int i=1;i<=tot0;i++) a[L+i-1]=a0[i];
61     for(int i=1;i<=tot1;i++) a[L+tot0+i-1]=a1[i];
62     dp(l,r);
63     for(int i=1;i<=tot;i++)
64     {
65         int tmp=INF;
66         for(int j=0;j<=b[i].sum;j++)
67         {
68             int t=max(f[b[i].l][j], g[b[i].r][b[i].sum-j]);
69             tmp=min(tmp,t);
70         }
71         if(tmp<=b[i].c) b[i].ansv=1;
72         else             b[i].ansv=0;
73     }
74     for(int i=1;i<=tot;i++) a[L+tot0+tot1+i-1]=b[i];
75     solve(l,mid,L,L+tot0-1);
76     solve(mid+1,r,L+tot0,L+tot0+tot1-1);
77 }
78 
79 int main()
80 {
81 //    freopen("test.txt","r",stdin);
82     int T;
83     scanf("%d",&T);
84     while(T--)
85     {
86         scanf("%d%d",&n,&m);
87         for(int i=1;i<=n;i++) scanf("%d",&v[i]);
88         for(int i=1;i<=n;i++) scanf("%d",&d[i]);
89         for(int i=1;i<=m;i++)
90         {
91             scanf("%d%d%d%d",&a[i].l,&a[i].r,&a[i].c,&a[i].sum);
92             a[i].id=i;
93         }
94         solve(1,n,1,m);
95         for(int i=1;i<=m;i++) ansv[a[i].id]=a[i].ansv;
96         for(int i=1;i<=m;i++) putchar(ansv[i]? '0':'1');
97         putchar('
');
98     }
99 }

View Code