2019年杭电多校第二场 1002题Beauty Of Unimodal Sequence(LIS+单调栈)

心已赠人 2021-11-01 03:30 176阅读 0赞

# 题目链接 #

[传送门][Link 1]

# 思路 #

首先我们对\\(a\\)正反各跑一边\\(LIS\\)，记录每个位置在前一半的\\(LIS\\)中应该放的位置\\(ans1\[i\]\\)，后一半的位置\\(ans2\[i\]\\)。

对于字典序最小的方案，我们找到第一个峰值，然后往前遍历。在\\(i\\)这个位置，如果它在\\(LIS\\)中放的位置是\\(pos\\)，那么我们先看当前放在\\(pos+1\\)的值是否比它大，大的话就说明这个位置一定比前面放过在\\(pos\\)这个位置的更优(因为字典序更小，且\\(\[1,i\]\\)一定可以放满\\(\[1,pos-1\]\\))，然后我们就用单调栈把当前放的小于等于\\(pos\\)的值全部\\(pop\\)掉。对于后一半的我们就直接对于每个可以放的位置反复覆盖即可。

对于字典序最大的我们则就是前一半反复覆盖，后一半用单调栈维护，与字典序刚好相反。

# 代码实现如下 #

#include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define lson rt<<1 #define rson rt<<1|1 #define lowbit(x) x&(-x) #define name2str(name) (#name) #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl #define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin) #define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-8; const int mod = 998244353; const int maxn = 3e5 + 7; const double pi = acos(-1); const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3fLL; int n; stack<int> st; vector<int> vec, v; int pos[maxn]; int a[maxn], dp[maxn], ans1[maxn], ans2[maxn]; int main() { #ifndef ONLINE_JUDGE FIN; #endif while(~scanf("%d", &n)) { memset(dp, inf, sizeof(dp)); dp[0] = 0; for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); ans1[i] = ans2[i] = 0; pos[i] = inf; ans1[i] = lower_bound(dp + 1, dp + n + 1, a[i]) - dp; dp[ans1[i]] = a[i]; } memset(dp, inf, sizeof(dp)); dp[0] = 0; for(int i = n; i >= 1; --i) { ans2[i] = lower_bound(dp + 1, dp + n + 1, a[i]) - dp; dp[ans2[i]] = a[i]; } while(!st.empty()) st.pop(); int idx = 1, mx = ans1[1] + ans2[1]; for(int i = 2; i <= n; ++i) { if(ans1[i] + ans2[i] > mx) { idx = i; mx = ans1[i] + ans2[i]; } } pos[ans1[idx]] = a[idx]; for(int i = idx - 1; i >= 1; --i) { if(ans1[i] >= ans1[idx]) continue; if(pos[ans1[i]+1] <= a[i]) continue; while(!st.empty() && ans1[i] >= ans1[st.top()]) { pos[ans1[st.top()]] = inf; st.pop(); } st.push(i); pos[ans1[i]] = a[i]; } vec.clear(); while(!st.empty()) { vec.push_back(st.top()); st.pop(); } vec.push_back(idx); int las = idx; for(int i = idx + 1; i <= n; ++i) { if(ans2[i] == ans2[las] - 1 && a[i] < a[las]) { vec.push_back(i); las = i; } } int flag = 0; for(auto x:vec) { if(flag) printf(" "); flag = 1; printf("%d", x); } printf("\n"); vec.clear(); idx = 1, mx = ans1[1] + ans2[1]; for(int i = 2; i <= n; ++i) { if(ans1[i] + ans2[i] >= mx) { idx = i; mx = ans1[i] + ans2[i]; } } las = idx; vec.push_back(idx); for(int i = idx - 1; i >= 1; --i) { if(ans1[i] == ans1[las] - 1 && a[i] < a[las]) { vec.push_back(i); las = i; } } reverse(vec.begin(), vec.end()); for(int i = 1; i<= n; ++i) pos[i] = inf; pos[ans2[idx]] = a[idx]; while(!st.empty()) st.pop(); for(int i = idx + 1; i <= n; ++i) { if(ans2[i] > ans2[idx]) continue; if(a[i] >= pos[ans2[i]+1]) continue; while(!st.empty() && ans2[i] >= ans2[st.top()]) { pos[ans2[st.top()]] = inf; st.pop(); } st.push(i); pos[ans2[st.top()]] = a[i]; } v.clear(); while(!st.empty()) { v.push_back(st.top()); st.pop(); } reverse(v.begin(), v.end()); flag = 0; for(auto x:vec) { if(flag) printf(" "); flag = 1; printf("%d", x); } for(auto x:v) { if(flag) printf(" "); flag = 1; printf("%d", x); } printf("\n"); } return 0; }

转载于:https://www.cnblogs.com/Dillonh/p/11240083.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6592