考察:贪心
思路:
由贪心可得,最长上升子序列要求前面尽可能的小,最短上升子序列要求前面尽可能的大.如果没有<>的限制,那么最长上升子序列是1 2 3 4...n,最短上升子序列是n n-1...1.对于最长上升子序列,每有一个>说明前后需要互换位置,对于最短上升子序列,每有一个<说明前后也需要互换位置.如果是连续的>(<),说明最左端应当在最右端,就是reverse一遍>(<)覆盖范围的数组.
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 const int N = 200010;
6 int n,a[N],b[N];
7 char s[N];
8 void get_A()
9 {
10 for(int i=n;i>=1;i--) a[n-i+1] = i;
11 for(int i=1;i<n;i++)
12 {
13 int j = i;
14 while(j<n&&s[j]=='<') j++;
15 reverse(a+i,a+j+1);
16 i = j;
17 }
18 for(int i=1;i<=n;i++) printf("%d ",a[i]);
19 printf("\n");
20 }
21 void get_B()
22 {
23 for(int i=1;i<=n;i++) b[i] = i;
24 for(int i=1;i<n;i++)
25 {
26 int j = i;
27 while(j<n&&s[j]=='>') j++;
28 reverse(b+i,b+j+1);
29 i = j;
30 }
31 for(int i=1;i<=n;i++) printf("%d ",b[i]);
32 printf("\n");
33 }
34 int main()
35 {
36 int T;
37 scanf("%d",&T);
38 while(T--)
39 {
40 scanf("%d%s",&n,s+1);
41 get_A();
42 get_B();
43 }
44 return 0;
45 }
解决方案一
说实话完全没想到怎么构造...我果然菜啊.
这里还有一个神级思路二:
首先复习二分求最长上升子序列长度.我们可以发现,它为了求出最长的上升子序列,是将该长度下最小的元素放在该一类的末尾.那么我们可以根据<>的顺序构造最长上升子序列,为了序列最长,我们需要将小的数放序列末尾.同理为了序列最短,我们需要将大的数放前面.
这位大佬的思路GO ,里面很详细了,解释以下为什么那么赋值:最短上升子序列因为下标小的要尽量大,而先push都是最小的.而最长子序列下标小的尽量小,所以从后往前赋值.
1 #include <iostream>
2 #include <cstdio>
3 #include <vector>
4 #include <algorithm>
5 using namespace std;
6 const int N = 200010;
7 int n,a[N],b[N];
8 char s[N];
9 vector<vector<int> > asc,des;
10 void Get_A()
11 {
12 des.push_back(vector<int>());
13 int st = 0,pos = 1,p = n;
14 des.push_back(vector<int>());
15 des[0].push_back(pos);
16 for(int i=1;i<n;i++)
17 {
18 if(s[i]=='<')
19 {
20 des.push_back(vector<int>());
21 des[++st].push_back(++pos);
22 }else
23 des[st=0].push_back(++pos);
24 }
25 for(int i=des.size()-1;i>=0;i++)
26 for(int j=0;j<des[i].size();j++)
27 a[des[i][j]] = p--;
28 for(int i=1;i<=n;i++) printf("%d ",a[i]);
29 printf("\n");
30 }
31 void Get_B()
32 {
33 asc.push_back(vector<int>());
34 int st = 0,pos = 1,p = n;
35 asc[st].push_back(pos);
36 for(int i=1;i<n;i++)
37 {
38 if(s[i]=='>')
39 asc[st].push_back(++pos);
40 else
41 {
42 asc.push_back(vector<int>());
43 asc[++st].push_back(++pos);
44 }
45 }
46 for(int i=asc.size()-1;i>=0;i--)
47 for(int j=0;j<asc[i].size();j++)
48 b[asc[i][j]] = p--;
49 for(int i=1;i<=n;i++) printf("%d ",b[i]);
50 printf("\n");
51 }
52 int main()
53 {
54 int T;
55 scanf("%d",&T);
56 while(T--)
57 {
58 scanf("%d%s",&n,s+1);
59 asc.clear();
60 des.clear();
61 Get_A();
62 Get_B();
63 }
64 return 0;
65 }
神级思路二