Codeforces 1144G Two Merged Sequences
题目链接
https://codeforces.com/problemset/problem/1144/G
题目大意
给你一个长度为 $N$ 的序列 $A$，问是否可以把这个序列分解成一个严格上升数列和一个严格下降数列，如果可行输出方案。
题目分析
定义 $f[i][0/1]$ 为前 $i$ 个序列，采用 $A_i$ 作为严格上升数列的最后一位时严格下降数列的最大数，和采用 $A_i$ 作为严格下降数列的最后一位时严格上升数列的最小的数。那么 $A_{i + 1}$ 转移时可以选择加到 $A_i$ 后面或者接到 $A_i$ 所不在的数列的最后面。记录一下每一个数的来源即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 2e5 + 5;
int inf = 0x3f3f3f3f;
int n, m, t;
int a[maxn];
int f[maxn][2];
int fr[maxn][2];
vector <int> ans;
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j;
int x, y;
n = read();
for(i=1;i<=n;i++){
a[i] = read();
f[i][0] = -inf;
f[i][1] = inf;
}
f[1][0] = inf;
f[1][1] = -inf;
for(i=2;i<=n;i++){
if(f[i - 1][0] != -inf){
if(a[i] > a[i - 1]){
f[i][0] = f[i - 1][0];
fr[i][0] = 0;
}
if(f[i - 1][0] > a[i]){
f[i][1] = a[i - 1];
fr[i][1] = 0;
}
}
if(f[i - 1][1] != inf){
if(a[i] < a[i - 1] and f[i - 1][1] < f[i][1]){
f[i][1] = f[i - 1][1];
fr[i][1] = 1;
}
if(f[i - 1][1] < a[i] and f[i][0] < a[i - 1]){
f[i][0] = a[i - 1];
fr[i][0] = 1;
}
}
}
if(f[n][0] != -inf){
x = 0;
}else if(f[n][1] != inf){
x = 1;
}else{
printf("NO\n");
return 0;
}
for(i=n;i>0;i--){
ans.push_back(x);
x = fr[i][x];
}
reverse(ans.begin(), ans.end());
printf("YES\n");
for(auto x : ans){
printf("%d ", x);
}
printf("\n");
return 0;
}