[洛谷 3572][POI2014]PTA-Little Bird

题目链接

https://www.luogu.org/problemnew/show/P3572

题解

按照正常的状态转移方式,对于一个点\(i\),我们枚举能跳到这个点的点\(j\)来更新答案。

这么做的复杂度是\(O(qn^2)\)的,需要优化。

我们发现本题的转移有单调性,考虑使用单调队列优化DP。这样便把复杂度降到了\(O(qn)\)。

#include <cstdio>
#include <algorithm>
int a[1000005],que[1000005],f[1000005];
int main()
{
 int n,q;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
 scanf("%d",&q);
 while(q--)
 {
  int x,h,t37;//别问我为什么是这样的变量名(划掉)
  scanf("%d",&x);
  h=t37=1,que[1]=1;
  for(int i=2;i<=n;i++)
  {
   while(h<=t37&&i-que[h]>x)
    h++;
   if(a[que[h]]>a[i])f[i]=f[que[h]];
   else f[i]=f[que[h]]+1;
   while(h<=t37&&(f[que[t37]]>f[i]||(f[que[t37]]==f[i]&&a[que[t37]]<=a[i])))
    t37--;
   que[++t37]=i;
  }
  printf("%d\n",f[n]);
 }
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注