题解 P1725 【琪露诺】

兴安黑熊 · 2018-06-18 13:42:26 · 题解

感觉还是滑动窗口解决这个问题比较好，根据自己的习惯，一直使用deque来实现的滑动窗口，STL神奇，这东西真好，当然自己手工用数组写也行的。给定窗口区间[l,r], 用滑动窗口找到区间的dp最大值max，然后根据 dp[i]=max+a[i],就可以了。写的时候的误区：总是局限于DP 的前几个数，后来想到从0位置，最先跳到L位置，所以L是我们第一个dp循环的下标；另一个误区就是窗口的大小，窗口大小是固定的 r-l+1就是，所以窗口出队列的条件就是 i-front().num>=(r-l+1);i代表进入队列窗口元素的下标，最后从n开始找就行了，本题数据有点水。下面是代码：

#include <iostream>
#include <deque>
using namespace std;
const int inf=0x3f3f3f3f;
struct sa
{
    int val;
    int num;
};
int dp[200001];
int a[200001];
deque <sa> v;
int main()
{   struct sa tmp;
    int n,l,r,p;
    cin>>n>>l>>r;
   for(int i=0;i<=n;i++)
      cin>>a[i];
     p=0; dp[p]=0;

    for(int i=l;i<=n;i++)
    {
       while(!v.empty()&&dp[p]>=v.back().val)
            v.pop_back();
            tmp.num=p;tmp.val=dp[p];
       v.push_back(tmp);
       //cout<<"dp ="<<dp[p].val<<endl;
       if (p-v.front().num>=(r-l+1))//这里是p不是i
        v.pop_front();

       dp[i]=v.front().val+a[i];
               //cout<<p<<" "<<v.front().val<<" "<<dp[i].val<<endl;
       p++;
    }
   int ans=-inf;
   for(int i=n-r+1;i<=n;i++)
        ans=max(ans,dp[i]);
        cout<<ans<<endl;

    return 0;
}