【P3572】little bird（单调队列+DP）

一眼看上去这个题就要DP，可是应该怎么DP呢，我们发现，数据范围最多支持O（NlogN），但是这种DP貌似不怎么有，所以应该是O（N）算法，自然想到单调队列优化DP。

然后我们先考虑如果不用单调队列应该怎么转移，那么f[i]=min（f[k]） (i-k>m）+（a[k]<=a[i])。而min(f[k])可以用单调队列求出。

然后就是之后的几个错误点：

1.一定不能看反不等号的方向。。

2.队头要先设置为1，此题因为可以事先直接入队第一个所以把队尾也设置成1.

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define re register

#define wc 0.0000000001

using namespace std;

int f[],a[],s[],ans,m,n,x,q[];

int main()

{

    cin>>n;

    for(re int i=;i<=n;i++)

    {

        cin>>a[i];

        s[i]=s[i-]+a[i];

    }

    cin>>m;

    for(re int i=;i<=m;i++)

    {

        cin>>x;

        f[]=;

        int h=,t=;

        q[t]=;

        for(re int j=;j<=n;j++)

        {

            while(h<=t&&j-q[h]>x)

            h++;

            f[j]=f[q[h]]+(a[q[h]]<=a[j]);

            while(h<=t&&(f[j]<f[q[t]]||(f[j]==f[q[t]]&&a[j]>=a[q[t]])))

            t--;

            q[++t]=j;

        }

        cout<<f[n]<<endl;

    }

}

巴特西

【P3572】little bird（单调队列+DP）

最新文章

热门文章