Problem Codeforces #550 (Div3) - G.Two Merged Sequences
Time Limit: 2000 mSec
Problem Description
Two integer sequences existed initially, one of them was strictly increasing, and another one — strictly decreasing.
Strictly increasing sequence is a sequence of integers [x1<x2<⋯<xk][x1<x2<⋯<xk] . And strictly decreasing sequence is a sequence of integers [y1>y2>⋯>yl][y1>y2>⋯>yl] . Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.
Elements of increasing sequence were inserted between elements of the decreasing one (and, possibly, before its first element and after its last element) without changing the order. For example, sequences [1,3,4][1,3,4] and [10,4,2][10,4,2] can produce the following resulting sequences: [10,1,3,4,2,4][10,1,3,4,2,4] , [1,3,4,10,4,2][1,3,4,10,4,2] . The following sequence cannot be the result of these insertions: [1,10,4,4,3,2][1,10,4,4,3,2] because the order of elements in the increasing sequence was changed.
Let the obtained sequence be aa . This sequence aa is given in the input. Your task is to find any two suitable initial sequences. One of them should be strictly increasing, and another one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.
If there is a contradiction in the input and it is impossible to split the given sequence aa into one increasing sequence and one decreasing sequence, print "NO".
Input
The first line of the input contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of elements in aa.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤2⋅1050≤ai≤2⋅105), where aiai is the ii-th element of a.
Output
If there is a contradiction in the input and it is impossible to split the given sequence aa into one increasing sequence and one decreasing sequence, print "NO" in the first line.
Otherwise print "YES" in the first line. In the second line, print a sequence of nn integers res1,res2,…,resnres1,res2,…,resn, where resiresi should be either 00 or 11 for each ii from 11 to nn. The ii-th element of this sequence should be 00 if the ii-th element of aa belongs to the increasing sequence, and 11 otherwise. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.
Sample Input
5 1 3 6 8 2 9 0 10
Sample Output
YES
1 0 0 0 0 1 0 1 0
题解：两种做法，先说贪心，维护下降序列当前最小值M和上升序列当前最大值m
1、a[i] > M && a[i] < m，自然无解。
2、a[i] < M && a[i] < m，只能加到下降序列。
3、a[i] > M && a[i] > m，只能加到上升序列。
4、a[i] < M && a[i] > m，此时需要考虑a[i+1]与a[i]的大小关系，不妨假设a[i+1] > a[i]，那么此时应将a[i]加入上升序列，原因很简单，如果把a[i]加入下降序列，则a[i+1]只能加入上升序列，显然这种方案不如把a[i]与a[i+1]都加入上升序列（下降的没动，上升的变化相同），另一种情况同理。
以上四点给出贪心算法并说明贪心成立。
第二种动态规划，分段决策类的动态规划，无非就是考虑第i个数加到上升还是下降，所以很容易想到二维dp，第一维表处理到第i个数，第二维表加入哪个序列，难想的地方在于要优化什么东西，这里的状态定义就很值得学习了：
dp(i, 0)表示处理完前i个数，将i加入递增序列后递减序列元素中最后一个元素的最大值。
dp(i, 1)表示处理完前i个数，将i加入递减序列后递增序列元素中最后一个元素的最小值。
我们肯定是希望前者越大越好，后者越小越好，这样给后面的数字提供更大的选择空间，其实这样定义状态看似有点绕，其实很合理，因为把i加入递增序列后，递增序列的最小值就有了，所以只需要再维护一下递减的最大值即可，加入递减序列同理。再说状态转移的问题，一般动态规划都是难在状态，此题也不例外，转移不难，就是枚举a[i]和a[i-1]分别放在哪种序列中即可，转移时要记录路径，方便最后输出。
贪心代码没啥说的就不贴了，只给出dp代码。
#include <bits/stdc++.h> using namespace std; #define REP(i, n) for (int i = 1; i <= (n); i++)
#define sqr(x) ((x) * (x)) const int maxn = + ;
const int maxm = + ;
const int maxs = + ; typedef long long LL;
typedef pair<int, int> pii;
typedef pair<double, double> pdd; const LL unit = 1LL;
const int INF = 0x3f3f3f3f;
const LL mod = ;
const double eps = 1e-;
const double inf = 1e15;
const double pi = acos(-1.0); int n;
int a[maxn], dp[maxn][];
int path[maxn][];
int ans[maxn]; int main()
{
ios::sync_with_stdio(false);
cin.tie();
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n;
for (int i = ; i <= n; i++)
{
cin >> a[i];
}
dp[][] = INF, dp[][] = -INF;
for (int i = ; i <= n; i++)
{
dp[i][] = -INF, dp[i][] = INF;
if (a[i - ] < a[i] && dp[i][] < dp[i - ][])
{
dp[i][] = dp[i - ][];
path[i][] = ;
}
if (dp[i - ][] > a[i] && dp[i][] > a[i - ])
{
dp[i][] = a[i - ];
path[i][] = ;
}
if (a[i] > dp[i - ][] && dp[i][] < a[i - ])
{
dp[i][] = a[i - ];
path[i][] = ;
}
if (a[i] < a[i - ] && dp[i][] > dp[i - ][])
{
dp[i][] = dp[i - ][];
path[i][] = ;
}
}
if(dp[n][] > -INF)
{
cout << "YES" << endl;
int opt = ;
for(int i = n; i >= ; i--)
{
ans[i] = opt;
opt = path[i][opt];
}
for(int i = ; i <= n; i++)
{
cout << ans[i] << " ";
}
}
else if(dp[n][] < INF)
{
cout << "YES" << endl;
int opt = ;
for(int i = n; i >= ; i--)
{
ans[i] = opt;
opt = path[i][opt];
}
for(int i = ; i <= n; i++)
{
cout << ans[i] << " ";
}
}
else
{
cout << "NO";
}
return ;
}