CF1304D Shortest and Longest LIS

佚名 4年前 (2020-02-25) 算法 617人围观抢沙发百度已收录

D. Shortest and Longest LIS

原题

Problem Restatement

给出一个序列相邻的大小关系，构造相应长度满足大小关系的排列，使得最长上升子序列最短或最长。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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;
}