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

题目链接

https://www.luogu.org/problem/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,t;
  scanf("%d",&x);
  h=t=1,que[1]=1;
  for(int i=2;i<=n;i++)
  {
   while(h<=t&&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<=t&&(f[que[t]]>f[i]||(f[que[t]]==f[i]&&a[que[t]]<=a[i])))
    t--;
   que[++t]=i;
  }
  printf("%d\n",f[n]);
 }
 return 0;
}