CF-1144

Posted on | Edited on | In | Views:

F. Graph Without Long Directed Paths

题意

一个严格递增的数列, 一个严格递减的数列, 将它们保持原相对顺序不变合并在一起. 给出合并后的数列.

题解1 (greedy)

维护一个递增数列 A, 一个递减的数列 B, 当只能插入一个数列的时候插入对应数列, 当两个都不能插入时输出”NO”, 当两个都能插入时, 若下一个数大于当前数, 插入 A, 否则插入 B.

题解2 (dp)

$dp[ i ][ 0 ]$表示处理完前 $i$ 个， 第 $i$ 个是递增序列序列里的元素，递减序列的最大值。

$dp[ i ][ 1 ]$表示处理完前 $i$ 个， 第 $i$ 个是递减序列序列里的元素，递增序列的最小值。

https://www.cnblogs.com/CJLHY/p/10634175.html

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int a[N],flag[N];
vii Inc,Dec;
int main() {
#ifdef PerpEternal
    // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    in(n);
    for0(i,n)in(a[i]);
    Inc.pb(-1);
    Dec.pb(3e5);
    for0(i,n){
        if(Inc.back()>=a[i]&&Dec.back()<=a[i]){
            puts("NO");
            return 0;
        }
        if(Inc.back()>=a[i]){
            flag[i]=1;
            Dec.pb(a[i]);
            continue;
        }
         if(Dec.back()<=a[i]){
            Inc.pb(a[i]);
            continue;
        }
        if(a[i+1]>a[i]){
            Inc.pb(a[i]);
        }else {
            flag[i]=1;
            Dec.pb(a[i]);
        }
    }
    puts("YES");
    for0(i,n)printf("%d ",flag[i]);
    puts("");
    return 0;
}