题解 P1725 【琪露诺】

Tardis · 2017-07-26 19:08:33 · 题解

首先这是一道动态规划的题目

如果不优化的话 只能得到部分分 要优化 必须用单调队列，线段树等等。（看到楼下写单调队列的挺少的，那我就来一个单调队列优化dp的）

首先明确 精灵只能从[i+l,i+r]转移过来 那么状态转移方程 ：

dp[i]=max(dp[k]) (k∈[i+l,i+r]) +a[i]; 因为题意说可以由大于n的数转移 那么就新增一个点 dp[n+1]=0；(主要还是避免负数)

明确一下 q为单调队列 维护的是从[i+l,i+r] dp[k]的最大值 （递减的）

首先dp[n-l+1]~dp[n]只能等于a[i] 先预处理一下

然后枚举i从n+1到l每次用dp[i]来更新dp[i-l] 然后把dp[i-l]打入单调队列 同时进行判断 如果i-1中右端点发生改变 那么就在i这个循环的末尾进行单调队列弹出队首元素

具体我们看一下代码

#include<iostream>
#include<cstdio>
using namespace std;
#define N 200001
int dp[N],a[N],n,l,r;
int q[N][2],head=1,tail=0;
int main()
{
    scanf("%d%d%d",&n,&l,&r);
    if(l>r) swap(l,r);//防止l比r大
    for(int i=0;i<=n;i++) scanf("%d",&a[i]);
    for(int i=n;i>=n-l+1;i--)
    {
        dp[i]=a[i];
    }
    for(int i=n+1;i>=l;i--)
    {
        while(tail>=head&&dp[i]>q[tail][0]) tail--;
        tail++;
        q[tail][0]=dp[i];
        q[tail][1]=i;
                //以上为将dp[i]打入单调队列
        dp[i-l]=q[head][0]+a[i-l];//更新
        if(i+r==q[head][1]) head++;//弹出
    }
    cout<<dp[0];
}