D. Shortest and Longest LIS
原題
Problem Restatement
給出一個序列相鄰的大小關系，構造相應長度滿足大小關系的排列，使得最長上升子序列最短或最長，
Solution
考慮到給出的是相鄰的遞增遞減，我們會發現序列是由一段上坡一段下坡類似組合而成，而上坡的地方肯定是最長上升子序列，
定義：坑 = 一個下坡（或沒有）+一個上坡，
所以我們可以很容易得出最短的最長上升子序列，最短為其中最長的“上坡”，那么我們只需要保證這些上坡不會被前面和后面續上即可，我們實際構造采取貪心，從最左邊的坑開始從大到小填數即可，
同理，最長的最長上升子序列，即讓所有的上坡都續上，可以證明續上最多可以為（上坡的元素個數之和 - 上坡的個數 + 1），同樣，貪心構造即可，從左邊開始，下坡倒著填，上坡順著填，
Code
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
int n,m,a[MAXN];
char s[MAXN];
void solve(){
int cnt,rcnt;
scanf("%d", &n);
scanf("%s", s);
memset(a,0,n*sizeof(a[0]));
rcnt=n;
for(int i=0,j,k;i<=n-1;i=j+1){
while(i<=n-2 && s[i]=='>') a[i++]=rcnt--;
for(j=i;j<=n-2 && s[j]=='<';j++);
for(k=j;k>=i;k--) a[k]=rcnt--;
}
for(int i=0;i<n;i++) printf("%d ", a[i]);
puts("");
memset(a,0,n*sizeof(a[0]));
cnt=1,rcnt=n;
if(s[n-2]=='<') a[n-1]=rcnt--;
for(int i=0;i<=n-2;i++){
if(s[i]=='<') a[i]=cnt++;
else a[i]=rcnt--;
}
if(s[n-2]=='>') a[n-1]=cnt;
for(int i=0;i<n;i++) printf("%d ", a[i]);
puts("");
}
int main(){
int T=1;
scanf("%d", &T);
while(T--){
solve();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83477.html
標籤：其他
上一篇：GMOJ5409.【GDOI2017模擬一試4.11】平行宇宙
下一篇：兩個鏈表的第一個公共結點