洛谷P1020 导弹拦截

n²谁都会打，不说了。

这里讨论一下nlogn算法(单调不减)：

首先开始考虑单调性，我习惯性的以为是单调队列/栈优化的那个套路，想要找到一个跟下标有关的单调性却发现没有。

例如：我想过当下标增加时f[i]增加，后来发现了反例：1 3 4 2

事实上也没有别的想得到的了。

我跑去看题解，发现单调性是这个毒瘤：

当单调不减子序列长度增加时，每个长度对应的最小高度增加。

然后每次二分出一个长度，保证最小高度刚好不大于a[i]

然后用a[i]更新f[i]的最小高度...

然后就没啥难点了，A了。

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 const int N = ;

 int a[N], f[N], p[N], top;

 inline int BS(int x) {

     int l = , r = top, mid;

     while(l < r) {

         mid = (l + r + ) >> ;

         if(p[mid] < x) {

             r = mid - ;

         }

         else {

             l = mid;

         }

     }

     return r;

 }

 inline int BS2(int x) {

     int l = , r = top, mid;

     while(l < r) {

         mid = (l + r + ) >> ;

         if(p[mid] >= x) {

             r = mid - ;

         }

         else {

             l = mid;

         }

     }

     return r;

 }

 int main() {

     int n = , x;

     while(scanf("%d", &x) != -) {

         a[++n] = x;

     }

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

         int t = BS(a[i]);

         f[i] = t + ;

         p[f[i]] = std::max(p[f[i]], a[i]);

         top = std::max(top, f[i]);

     }

     printf("%d \n", top);

     top = ;

     memset(p, 0x7f, sizeof(p));

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

         int t = BS2(a[i]);

         f[i] = t + ;

         p[f[i]] = std::min(p[f[i]], a[i]);

         top = std::max(top, f[i]);

     }

     printf("%d", top);

     return ;

 }

AC代码

附一张提交记录

巴特西

洛谷P1020 导弹拦截

最新文章

热门文章