little bird

LITTLE BIRD

Bzoj 3831

相对而言是一道比较简单的DP，不过它需要用单调队列优化。首先是朴素O（n²）,

if(d[j]>f[i])

f[i]=min(f[i],f[j]);

else

f[i]=min(f[i],f[j]+1);

f[i]表示从1到i需要的最少代价

K很大时会很慢

 1 #include<bits/stdc++.h>
 2 
 3 #define INF 9999999
 4 
 5 using namespace std;
 6 
 7 int n,k;
 8 
 9 int f[1000000];
10 
11 int d[1000000];
12 
13 int main()
14 
15 {
16 
17 cin>>n>>k;
18 
19 memset(f,INF,sizeof(f));
20 
21 f[1]=0;
22 
23 for(int i=1;i<=n;i++)
24 
25 cin>>d[i];
26 
27 for(int i=1;i<=n;i++)
28 
29 {
30 
31 for(int j=i-k;j<i;j++)
32 
33 {
34 
35 if(d[j]>d[i])
36 
37 f[i]=min(f[i],f[j]);
38 
39 else
40 
41 f[i]=min(f[i],f[j]+1);
42 
43 }
44 
45 }
46 
47 cout<<f[n];
48 
49 return 0;
50 
51 }

然后是单调队列优化，O（n）的复杂度，对于两个位置i、j，i在j之后，如果f[i]<f[j],直接抛弃j，如果f[i]==f[j],那再h[i]>=h[j],也是抛弃j，即tail--，最后i入队。队列的单调性是单调递增的，每次取队首就可以了。

优化过后，果然很快。

#include<bits/stdc++.h>

using namespace std;

int top,tail,q[1000001];

int f[1000001];

int n,k;

int d[1000001];

bool cmp(int f1,int h1,int f2,int h2)

{

return f1==f2?h1>=h2:f1<f2;

}

 

int main()

{

    cin>>n>>k;

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

    cin>>d[i];

    q[top=tail=1]=1;

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

    {

     while(top<=tail&&i-top>k)top++;

     f[i]=f[q[top]]+(d[i]>=d[q[top]]?1:0);

     while(top<=tail&&cmp(f[i],d[i],f[tail],d[tail]))tail--;

     q[++tail]=i;

}

cout<<f[n];

return 0;

}