【清真dp】cf1144G. Two Merged Sequences

成就：赛后在cf使用错误的贪心通过一题

成就：在cf上赛后提交hack数据

成就：在cf上赛后hack自己

题目大意

有一长度$n \le 2\times 10^5$的序列，要求判断是否能够划分为一个严格递增和一个严格递减的子序列并给出划分方案。

题目分析

错误的贪心

截止现在（4.22），这一种错误贪心尚可以通过此题。

算法流程：考虑处理出一个LIS和一个LDS，并检查剩下的元素是否为LDS/LIS.

这个算法在随机构造下是基本没问题的（因此跑了47000+组随机数据才rand出一组反例）。

事实上，如果枚举每一个LIS/LDS，这个做法就是显然正确的，但是复杂度会有相当影响（例如一个完全非法但是LIS/LDS非常多的数列）

清真dp

记$f_{i,0}$为：$i$处在一个上升子序列中，$1\cdots i-1$的下降子序列最高为$f_{i,0}$；$f_{i,1}$同理。

这个状态显然是需要贪心取最大/最小的，那么这个转移就可以做到$O(1)$，相当高效。

 #include<bits/stdc++.h>

 const int maxn = ;

 const int INF = 2e9;

 int n,a[maxn],p[maxn][],f[maxn][];

 int read()

 {

     char ch = getchar();

     int num = , fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = -;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     return num*fl;

 }

 void print(int x, int c)

 {

     if (x > ) print(x-, p[x][c]);

     printf("%d ",c);

 }

 int main()

 {

     n = read();

     for (int i=; i<=n; i++) a[i] = read();

     f[][] = INF, f[][] = -INF;

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

     {

         f[i][] = -INF, f[i][] = INF;

         if (a[i] > a[i-]&&f[i][] < f[i-][]) f[i][] = f[i-][], p[i][] = ;

         if (a[i] < a[i-]&&f[i][] > f[i-][]) f[i][] = f[i-][], p[i][] = ;

         if (a[i] > f[i-][]&&f[i][] < a[i-]) f[i][] = a[i-], p[i][] = ;

         if (a[i] < f[i-][]&&f[i][] > a[i-]) f[i][] = a[i-], p[i][] = ;

     }

     if (f[n][]!=-INF) puts("YES"), print(n, ), exit();

     if (f[n][]!=INF) puts("YES"), print(n, ), exit();

     puts("NO");

     return ;

 }

END

巴特西

【清真dp】cf1144G. Two Merged Sequences

题目大意

题目分析

错误的贪心

清真dp

最新文章

热门文章