51nod 1153 选择子序列

桃扇骨 2021-10-26 18:28 266阅读 0赞

[51nod 选择子序列][51nod]

这道题是[\\(Bunny\\)][Bunny]学长在给我们的模拟赛中的一道题。

食用单调栈，处理每个数\\(a\_i\\)左右第一个比自己大的数的下标\\(left\_i\\)，\\(right\_i\\)，并且建两条有向边\\((i,left\_i)\\)，\\((i,right\_i)\\)。处理完毕后得到一个\\(DAG\\)。

然后求此图的拓扑序。由于都是小数连大数，所以可以以\\(a\_i\\)的值为关键字排序，\\(sort\\)后即得到此\\(DAG\\)的一个拓扑序。

求得拓扑序后，即可\\(O(n)\\) \\(DP\\) 求\\(DAG\\)最长链。最长链即为\\(ans\\)。

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <stack> #define MAXN 100233 using namespace std; struct qmq { int id,x; }a[MAXN]; int n; struct qwq { int id,x; }; stack<qwq> x,y; int l[MAXN],r[MAXN]; struct qvq { int nex,to; }e[MAXN<<1]; int tot=0,h[MAXN]={}; int f[MAXN]; inline void add(int u,int v) { // printf("Edge:::%d %d\n",u,v); e[++tot].to=v; e[tot].nex=h[u]; h[u]=tot; } bool cmp(qmq o,qmq t) { return o.x<t.x; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i].x); a[i].id=i; } for (int i=1;i<=n;i++) { while (!x.empty()&&x.top().x<=a[i].x) { if (x.top().x==a[i].x) { r[x.top().id]=0; x.pop(); continue; } r[x.top().id]=i; x.pop(); } x.push((qwq){i,a[i].x}); } for (int i=n;i;i--) { while (!y.empty()&&y.top().x<=a[i].x) { if (y.top().x==a[i].x) { l[y.top().id]=0; y.pop(); continue; } l[y.top().id]=i; y.pop(); } y.push((qwq){i,a[i].x}); } for (int i=1;i<=n;i++) { if (r[i]) add(i,r[i]); if (l[i]) add(i,l[i]); } sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++) { // printf(":::::::::::::::%d\n",a[i].id); f[a[i].id]=max(f[a[i].id],1); for (int j=h[a[i].id];j;j=e[j].nex) { f[e[j].to]=max(f[e[j].to],f[a[i].id]+1); } } int ans=-233333; for (int i=1;i<=n;i++) { ans=max(ans,f[i]); } printf("%d",ans); return 0; }

转载于:https://www.cnblogs.com/Kan-kiz/p/11310225.html

[51nod]: http://www.51nod.com/Challenge/Problem.html#problemId=1153
[Bunny]: https://www.cnblogs.com/bunnycxk