思路:
dp。
實作:
1 #include <bits/stdc++.h>
2 using namespace std;
3 int a[100005], dp[100005][6];
4 int main()
5 {
6 int n;
7 while (cin >> n)
8 {
9 for (int i = 1; i <= n; i++) cin >> a[i];
10 memset(dp, 0, sizeof dp);
11 for (int i = 1; i <= 5; i++) dp[1][i] = 1;
12 for (int i = 2; i <= n; i++)
13 {
14 for (int j = 1; j <= 5; j++)
15 {
16 if (a[i] > a[i - 1])
17 {
18 for (int k = 1; k < j; k++)
19 {
20 if (dp[i - 1][k]) dp[i][j] = k;
21 }
22 }
23 else if (a[i] < a[i - 1])
24 {
25 for (int k = j + 1; k <= 5; k++)
26 {
27 if (dp[i - 1][k]) dp[i][j] = k;
28 }
29 }
30 else
31 {
32 for (int k = 1; k <= 5; k++)
33 {
34 if (k != j && dp[i - 1][k]) dp[i][j] = k;
35 }
36 }
37 }
38 }
39 bool flg = false;
40 int i = 1;
41 for ( ; i <= 5; i++)
42 {
43 if (dp[n][i]) { flg = true; break; }
44 }
45 if (!flg) cout << "-1" << endl;
46 else
47 {
48 vector<int> v;
49 v.push_back(i);
50 int now = n;
51 while (now >= 2)
52 {
53 v.push_back(dp[now][i]);
54 i = dp[now][i];
55 now--;
56 }
57 for (int i = v.size() - 1; i >= 0; i--) cout << v[i] << " ";
58 cout << endl;
59 }
60 }
61 return 0;
62 }
轉載于:https://www.cnblogs.com/wangyiming/p/10054219.html