题解 P1725 【琪露诺】

· · 题解

相信读完题就能看出这是一道简单的dp题

状态转移方程也很容易想到

即：dp[i] = max{区间内的最大dp值}+该点的权值

这种算法的最坏复杂度为O(n^2)，而本题的数据是1e5级别的，这样的复杂度显然不正确，必须优化

优化

哪一步可以优化呢？

我们又发现每次跳的区间都是一个固定长度，自然而然地想到了一个经典的问题：滑动窗口问题，即单调队列，可以让我们做到O(n)预处理，O(1)找到任意固定长度区间内的最值不要尝试在没有学会单调队列的情况下做这道题

有了单调队列，我们的dp过程可以省去枚举区间内的每个元素的过程，总复杂度也由O(n^2)降到O(n)，完全没有压力

如何实现

在代码中由注释进行讲解

#include<cstdio>
using namespace std;
#define oo 0x3f3f3f3f 
#define ri register int
const int N = 200005;
int n,l,r,head = 1,tail = 0,cur = 0,ans = -oo,a[N],q[N],dp[N];
//head,tail分别是单调队列的首尾指针,cur是指向当前待入队列的元素，a存权值，q为单调队列(手打) 
inline int max( int a , int b ){return a > b ? a : b; }//手打max 
template<class T>
inline void read(T &res){
    static char ch;T flag = 1;
    while( ( ch = getchar() ) < '0' || ch > '9' ) if( ch == '-' ) flag = -1;
    res = ch - 48;
    while( ( ch = getchar() ) >= '0' && ch <= '9' ) res = res * 10 + ch - 48;
    res *= flag;
}//快读 
int main()
{
    read( n );read( l );read( r );
    for( ri i = 0 ; i <= n ; i++ ) read( a[ i ] );
    for( ri i = 1 ; i <= n ; i++ ) dp[ i ] = -oo;//初始化 
    for( ri i = 1 ; i <= n ; i++ ){
        //由于一个点可到达的区间为[i+l,i+r],因此可以到达一个点的区间为[i-r,i-l],注意不要越界 
        while( i - cur >= l ){//让能够入队的结点入队 
            while( head <= tail && dp[ cur ] >= dp[ q[ tail ] ] ) tail--;
            //由于单调队列是单调递减的，所以我们要删除队尾那些dp值小于待入队结点dp值的结点 
            q[ ++tail ] = cur++;//入队 
        }
        while( head <= cur && i - q[ head ] > r ) head++;
        //如果队列的头已经不再界限内，则不可能再更新当前 
        if( head <= tail )//注意，当队列不为空时才可以转移 
          dp[ i ] = dp[ q[ head ] ] + a[ i ];
    }
    //因为题目说只要下一步的位置编号大于N就算到达对岸 
    //所以最后得出答案，为区间[n-r+1,n]中的dp最大值 
    for( ri i = n ; i >= n - r + 1 ; i-- )
      ans = max( ans , dp[ i ] );
    printf( "%d\n" , ans );
    return 0;
}

如果嫌这道题太简单，可以尝试PP3957 跳房子

感谢观看！