首页 > 其他 > 详细

P2627 修剪草坪 (单调队列优化DP)

时间:2019-07-19 09:08:50      阅读:126      评论:0      收藏:0      [点我收藏+]

题目链接

Solution

70分很简单的DP,复杂度 O(NK)。
方程如下:
\[f[i][1]=max(f[j][0]+sum[i]-sum[j])\]\[f[i][0]=max(f[i-1][1],f[i-1][0])\]
然后就要考虑优化,很显然可以用单调队列来优化。
维护当前 \(i\) 的前 \(k\) 个点中 \(f[j][0]\)\(max\) 值转移即可。
复杂度 O(N) 。

Code

#include<bits/stdc++.h>
#define N 100008
#define ll long long
using namespace std;

ll n,k,c[N];
ll f[N][2],sum[N];
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&c[i]),sum[i]=sum[i-1]+c[i];
    ll head=1,tail=1,a[N];
    a[1]=0;
    for(int i=1;i<=n;i++)
    {
        f[i][1]=f[a[head]][0]+sum[i]-sum[a[head]];
        f[i][0]=max(f[i-1][1],f[i-1][0]);
        while(1)
            if(f[i][0]>=f[a[tail]][0]+sum[i]-sum[a[tail]]&&tail>=head)
                {tail--;}
            else break;
        a[++tail]=i;
        while(1)
            if(a[head]<i+1-k)head++;
            else break;
        if(tail<head)tail=head;
    }cout<<max(f[n][0],f[n][1])<<endl;
}
/*
7 2
1 7 8 4 5 9 10
Ans: 34
*/

P2627 修剪草坪 (单调队列优化DP)

原文:https://www.cnblogs.com/Kv-Stalin/p/11210770.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!