洛谷P2686 【老虎的题目】

发表于 | 更新于 | 分类于 | 阅读次数：

这题确实可以通过一些微妙的做法，巧妙的将复杂度降低，但是并不具有 通用性。

做法依然是DP，设$f[i][j]$表示从第i个题目，到第j个题目可达到的最大值。

一个不难想出的式子是：

当$low<=l[j]-l[i-1]<=high$时，$f[i][j]=max(f[x][y] |x<i,y<j)+d[j]-d[i-1]$，其中d[i]是从$1-i$题目难度的前缀和。

所以暴力的做法，我们需要$O(N^4)$的DP转移，得出$f[1][n]$即为答案。

显然时间肯定是爆炸的，一个正常的想法就是通过一写数据结构维护DP的最大值，来达到降低复杂度的目的。

看到二维区间的求最大值问题，便可以用二维线段树实现：

顾名思义，二维线段树就是在一棵线段树的每一个节点，都保存着另一棵线段树的根节点编号。
为了实现这两种功能，我们需要建一棵外层线段树(可以动态开点也可以静态开点)，对于外层线段树的每一个节点，我们都保存一个内层线段树的根节点编号(内层线段树必须动态开点，否则MLE)。
查询时与普通线段树很像，但要在锁定一维后在内层线段树查找另一维，然后才能得出答案。

以上内容摘录此博客

对于每次查询，当处于搜索至(i,j)时，查询(1,1)至(i-1,j-1)的区间最大值，并将新的答案插入至(i,j)，可将复杂度将至$O(n^2*log^2(n))$。

然后就可以AC辣！
附上丑陋的代码_(:з」∠)_：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#define ll long long
using namespace std;
struct ot{
    int ls;
    int rs;
    int rt;
}otr[400000];
struct it{
    int ls;
    int rs;
    ll w;
}intr[500000];
int root;
ll gg,lw,hi,l1,d1,f[2000][2000],le[2000],di[2000],maxx;
ll n,m,cnt1,cnt2,ans,x,y,kk; //cnt-->动态开点个数

ll que_i(int &k,int l,int r,int y)
{
    if (!k) return 0;
    if (y>=r) return intr[k].w; //如果(l,r)在(0,y)区间内
    int mid=(l+r)/2;
    if (y<=mid) return que_i(intr[k].ls,l,mid,y);
    else return max(que_i(intr[k].ls,l,mid,y),que_i(intr[k].rs,mid+1,r,y)); 
}


ll que_o(int &k,int l,int r,int m,int x,int y)
{
    if (!k) return 0; 
    if (x>=r) return que_i(otr[k].rt,1,m,y); //如果(l,r)在(0,x)区间内
    int mid=(l+r)/2;
    if (x<=mid) return que_o(otr[k].ls,l,mid,m,x,y);
    else return max(que_o(otr[k].ls,l,mid,m,x,y),que_o(otr[k].rs,mid+1,r,m,x,y)); 
}

void add_i(int &k,int l,int r,int y,ll v)
{
    if (!k) k=++cnt2;
    intr[k].w=max(intr[k].w,v);
    if (l==r) return;
    int mid=(l+r)/2;
    if (y<=mid) add_i(intr[k].ls,l,mid,y,v);
    else add_i(intr[k].rs,mid+1,r,y,v);
} 

void add_o(int &k,int l,int r,int m,int x,int y,ll v)
{
    if (!k) k=++cnt1;
    add_i(otr[k].rt,1,m,y,v);
    if (l==r) return;
    int mid=(l+r)/2;
    if (x<=mid) add_o(otr[k].ls,l,mid,m,x,y,v);
    else add_o(otr[k].rs,mid+1,r,m,x,y,v);
} 
int main()
{
    cin>>n>>lw>>hi;
    for (int i=1;i<=n;i++) cin>>l1,le[i]+=le[i-1]+l1;
    for (int i=1;i<=n;i++) cin>>d1,di[i]+=di[i-1]+d1;
    for (int j=1;j<=n;j++)
    for (int i=1;i<=j;i++){
        if (le[j]-le[i-1]>=lw&&le[j]-le[i-1]<=hi){
        maxx=que_o(root,1,n,n,i-1,j-1);
		f[i][j]=maxx+di[j]-di[i-1]; add_o(root,1,n,n,i,j,f[i][j]);
        ans=max(ans,f[i][j]);
    }	
    }
    cout<<ans<<endl;
    return 0;
}