洛谷 P1725 琪露诺 题解【DP】【单调队列】【线段树】
点击量：152
一道O(N)的题又在考场上打了暴力线段树。。。
题目描述
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。
某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只移动到区间[i+l,i+r]中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。
每一个格子都有一个冰冻指数A[i]，编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。
开始时，琪露诺在编号0的格子上，只要她下一步的位置编号大于N就算到达对岸。
输入输出格式
输入格式：
第1行：3个正整数N, L, R
第2行：N+1个整数，第i个数表示编号为i-1的格子的冰冻指数A[i-1]
输出格式：
一个整数，表示最大冰冻指数。保证不超过2^31-1
输入输出样例
输入样例#1：5 2 30 12 3 11 7 -2输出样例#1：11说明
对于60%的数据：N<=10,000
对于100%的数据：N<=200,000
对于所有数据-1,000<=A[i]<=1,000且1<=L<=R<=N
解法：
首先我们看到，如果直接用刷表/填表的话，时间复杂度是$ O(N(R-L))=O(N^2)$的，肯定过不了。因此我们要考虑状态转移过程中的特征：如果是填表，从前面的[i-R,i-L]转移过来，取这些点中的最大值。如果是刷表，转移到[i+L,i+R]，更新这些点的最大值，后面写的线段树就是这种刷表做法。填表做法与下面讲的单调队列优化类似。
我们DP过程中转移的是区间最大值，那么我们可以用单队来维护一下。单队中所储存的区间是[i-R,i-L]，因此我们DP从第L个点开始，取递减单队中最大点进行转移。每次忽略掉小于i-R的，更新i-L到队列中，这样每次转移使得队列中元素单减。（这种优化也可以用堆实现，时间复杂度有区别）
因此，在区间最值转移的DP中，最优考虑的是单调队列，实在想不到可以用线段树、堆等。
Code：（单调队列）
#include<cstdio>
#include<cstring>
int q[210000],l=0,r=0;
int f[210000];
int a[210000];
int main()
{
//freopen("data.in","r",stdin);
//freopen("bf1.out","w",stdout);
memset(f,-0x3f,sizeof(f));
int n,L,R;
scanf("%d%d%d",&n,&L,&R);
for(int i=0;i<=n;i++)
scanf("%d",&a[i]);
//q[++r]=0;
f[0]=0;
for(int i=L;i<=n+1;i++)
{
if(l<r&&q[l+1]<i-R)//判断范围
l++;
while(l<r&&f[q[r]]<f[i-L])//判断单调性
r--;
q[++r]=i-L;
f[i]=f[q[l+1]]+a[i];
}
int ans=-0x3fffffff;
for(int i=q[l+1];i<=n+1;i++)
ans=f[i]>ans?f[i]:ans;
printf("%d\n",ans);
return 0;
}
Code：（线段树）
#include<cstdio>
#include<cstring>
#define inf 0x3fffffff
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
int max(int x,int y)
{
return x>y?x:y;
}
int min(int x,int y)//防止越界
{
return x<y?x:y;
}
struct node
{
int l,r,v,lazy,lazyn;
node(int l,int r,int v)
{
this->l=l;
this->r=r;
this->v=v;
lazy=-inf;
lazyn=0;
}
node(int l,int r)
{
this->l=l;
this->r=r;
lazy=-inf;
lazyn=0;
}
node()
{
lazy=-inf;
lazyn=0;
}
}t[1000000];
int a[210000];
void build(int k,int l,int r)
{
if(l==r)
{
t[k]=node(l,r,-inf);
return;
}
t[k]=node(l,r);
build(ls,l,mid);
build(rs,mid+1,r);
//区间值没用
}
int tmp,pre[201000];
void pushdown(int k)
{
if(t[k].l==t[k].r)
{
if(t[k].lazy>t[k].v)
{
t[k].v=t[k].lazy;
pre[t[k].l]=t[k].lazyn;
}
/*t[k].v=max(t[k].lazy,t[k].v);
pre[t[k].l]=t[k].lazyn;*/
t[k].lazy=-inf;
t[k].lazyn=0;
return;
}
if(t[k].lazy>t[ls].lazy)
{
t[ls].lazy=t[k].lazy;
t[ls].lazyn=t[k].lazyn;
}
if(t[k].lazy>t[rs].lazy)
{
t[rs].lazy=t[k].lazy;
t[rs].lazyn=t[k].lazyn;
}
t[k].lazy=-inf;
t[k].lazyn=0;
}
void change(int k,int l,int r,int x)
{
if(t[k].l==l&&t[k].r==r)
{
if(x>t[k].lazy)
{
t[k].lazy=x;
t[k].lazyn=tmp;
}
return;
}
pushdown(k);
if(r<=Mid)
change(ls,l,r,x);
else if(l>Mid)
change(rs,l,r,x);
else
{
change(ls,l,Mid,x);
change(rs,Mid+1,r,x);
}
}
int ask(int k,int p)
{
pushdown(k);
if(t[k].l==t[k].r)
return t[k].v;
if(p<=Mid)
return ask(ls,p);
else
return ask(rs,p);
}
int s[250000],top=0;//栈
int main()
{
//freopen("data.in","r",stdin);
//freopen("right.out","w",stdout);
int n,l,r;
scanf("%d%d%d",&n,&l,&r);
build(1,1,n+1);
for(int i=0;i<=n;i++)
scanf("%d",&a[i]);
a[n+1]=0;
//对0的初始化
change(1,l,r,0);
for(int i=l;i<=r;i++)
pre[i]=0;
for(int i=1;i<=n;i++)
{
tmp=i;//现在是谁在转移
change(1,min(i+l,n+1),min(i+r,n+1),ask(1,i)+a[i]);
}
//printf("%d\n%d\n",ask(1,3386),ask(1,3279));
printf("%d\n",ask(1,n+1));
int k=n+1;
s[++top]=-1;
while(k!=0)
{
s[++top]=pre[k];
k=pre[k];
}
/*for(int i=top;i>=1;i--)
printf("%d ",s[i]);*/
return 0;
}
说点什么