前置扯淡

%%@\(wucstido\)，思路是在是巧妙---link

Description

给一个长度为\(n\)由 \(<\) 和 \(>\)组成的字符串，表示序列中相邻位置的数的大小关系

求构造两种排列，使得其在满足上述条件的情况下的 \(LIS\) 分别最长\(/\)最短

Solution

直接考虑构造最短的排列，然后最长的同理（真的是把符号改改就可以了）

整个排列\(LIS\)的最小值在最长的一段\("<"\)中取得，然后我们考虑构造

先把整个排列逆序过来：即 \(a_i=n-i+1\)

然后对于每一个\("<"\)，翻转相邻的数字

正确性显然（真的是很巧妙！！！！！！）

最长的构造就是初始化正序，大于号翻转！就完事啦！！

别想复杂了，构造题就是构造题

Code

#include<bits/stdc++.h> 
using namespace std;
#define int long long
namespace yspm{
    inline int read()
    {
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res*f; 
    }
    const int N=2e5+10;
    char s[N]; int ans[N],n;
    inline void work()
    {
        n=read(); scanf("%s",s+1);
        for(int i=1;i<=n;++i) ans[i]=n-i+1;
        for(int i=1;i<n;++i)
        {
            int j=i; while(s[j]=='<') ++j; reverse(ans+i,ans+j+1); i=j;
        } for(int i=1;i<=n;++i) printf("%lld ",ans[i]); puts("");
        for(int i=1;i<=n;++i) ans[i]=i;
        for(int i=1;i<n;++i)
        {
            int j=i; while(s[j]=='>') ++j; reverse(ans+i,ans+j+1); i=j;
        } for(int i=1;i<=n;++i) printf("%lld ",ans[i]); puts(""); 
        return ;
    }
    signed main()
    {
        int T=read(); while(T--) work();
        return 0;
    }
}
signed main(){return yspm::main();}

Codeforces1304D Shortest and Longest LIS

原文：https://www.cnblogs.com/yspm/p/12317821.html