Shortest and Longest LIS

D - Shortest and Longest LIS

因为要使最长上升子序列分别为最小和最大，所以可以先分别让序列为n n-1 n-2 ...3 2 1和1 2 3...n-2 n-1 n，然后再让序列满足题给条件，要注意的是连续的“<”和连续的“>”应该进行翻转操作。

通过这道题应该想到的东西是，题给条件所要求的“>”、”<“是无法改变的，所以最一开始就应该让串本身是一个最优的串，然后再让串一步一步满足条件。

// Created by CAD on 2020/2/15.
#include <bits/stdc++.h>
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;

const int maxn=2e5+5;
int o[maxn];
void print(int n){
    for(int i=1;i<=n;++i)
        cout<<o[i]<<" \n"[i==n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        string s;cin>>s;
        for(int i=1;i<=n;++i)
            o[i]=n-i+1;
        for(int i=0;i<=n-2;++i){
            int j=i;
            while(j<=n-2&&s[j]=='<') ++j;
            if(i!=j)    reverse(o+i+1,o+j+2);
            i=j;
        }
        print(n);
        for(int i=1;i<=n;++i)
            o[i]=i;
        for(int i=0;i<=n-2;++i){
            int j=i;
            while(j<=n-2&&s[j]=='>') ++j;
            if(i!=j)    reverse(o+i+1,o+j+2);
            i=j;
        }
        print(n);
    }
    return 0;
}

Shortest and Longest LIS

原文：https://www.cnblogs.com/CADCADCAD/p/12316605.html