bzoj 3831 Little Bird (单调队列优化dp)

/*先贴个n*n的*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000010
using namespace std;
int n,k,h[maxn],f[maxn],Q;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&h[i]);
scanf("%d",&Q);
while(Q--)
{
scanf("%d",&k);
memset(f,/,sizeof(f));
f[]=;
for(int i=;i<=n;i++)
for(int j=i-k;j<i;j++)
{
if(j<=)continue;
if(h[i]>=h[j])f[i]=min(f[i],f[j]+);
if(h[i]<h[j])f[i]=min(f[i],f[j]);
}
printf("%d\n",f[n]);
}
return ;
}
/*
对于每次的查找最小值 用单调队列维护
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000010
using namespace std;
int n,k,h[maxn],f[maxn],Q,q[maxn],head,tail;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&h[i]);
scanf("%d",&Q);
while(Q--)
{
head=;tail=;
scanf("%d",&k);
f[]=;q[++tail]=;
for(int i=;i<=n;i++)
{
while(tail>=head&&i-q[head]>k)head++;
if(h[i]>=h[q[head]])f[i]=f[q[head]]+;
else f[i]=f[q[head]];
while(head<=tail&&f[i]<=f[q[tail]])
{
if(f[i]==f[q[tail]]&&h[i]<h[q[tail]])break;
tail--;
}
q[++tail]=i;
}
printf("%d\n",f[n]);
}
return ;
}
上一篇:iOS-改变UITextField的Placeholder颜色的三种方式


下一篇:《Java编程思想》学习笔记(二)——类加载及执行顺序