Two merged sequences (CF 1144 g) -dp

Topic link ;
Reference resources ;

Ideas

Build state representation ：
$dp[i][1]$ Representative in front i In a , Ruodi i Bit is the end of the ascending sequence , The maximum value at the end of the descending sequence ;
$op[i][1]$ For and on behalf of i Bit is the end of the ascending sequence ,$dp[i][1]$ When the current value is taken , The first i-1 Bits in ascending sequence / Descending sequence （1 l 0 drop ）;
$dp[i][0]$ Representative in front i In a , Ruodi i Bit is the end of the descending sequence , The minimum value at the end of the ascending sequence ;
$op[i][0]$ For and on behalf of i Bit is the end of the descending sequence ,$dp[i][0]$ When the current value is taken , The first i-1 Bits in ascending sequence / Descending sequence （1 l 0 drop ）;

Define the initial value ：
$dp[i][1]=-inf,dp[i][1]=inf$ That is, each bit cannot participate in the sequence by default , It can not be updated until the conditions are met when the equation is transferred ;
Specifically , $dp[1][1]=inf,dp[1][0]=-inf$ That is, the first bit can be in the ascending sequence , Or in descending sequence ;

State transition equation ：
$dp[i][1]=dp[i-1][1],op[i][1]=1;(a[i-1]<a[i]\&\&dp[i][1]<dp[i-1][1])$ This bit is followed by the preceding bit in ascending sequence
$dp[i][1]=a[i-1],op[i][1]=0;(dp[i-1][0]<a[i]\&\&dp[i][1]<a[i-1])$ The first bit ends the descending sequence , This bit ends the ascending sequence
$dp[i][0]=dp[i-1][0],op[i][0]=0;(a[i-1]>a[i]\&\&dp[i][0]>dp[i-1][0])$ This bit is followed by the preceding bit in descending order
$dp[i][0]=a[i-1],op[i][0]=1;(dp[i-1][1]>a[i]\&\&dp[i][0]>a[i-1])$ The preceding bit ends the ascending sequence , This bit ends the descending sequence
In the above two restrictions , The former condition determines the feasibility of this situation , The latter condition determines the necessity of making an update ;

about dp After the results of the , as long as $dp[i][j]$ Not the initial value , It means that there is a feasible solution in this case , adopt $op[i][j]$ The direction of the mark can be traced back ;

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x7f7f7f7f;
int a[200005];
int dp[200005][2];
int op[200005][2];
int opt[200005];
int main()
{
    
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    dp[1][1] = inf, dp[1][0] = -inf;
    for (int i = 2; i <= n; i++)
    {
    
        dp[i][1] = -inf, dp[i][0] = inf;
        if (a[i - 1] < a[i] && dp[i][1] < dp[i - 1][1])
        {
    
            dp[i][1] = dp[i - 1][1];
            op[i][1] = 1;
        }
        if (dp[i - 1][0] < a[i] && dp[i][1] < a[i - 1])
        {
    
            dp[i][1] = a[i - 1];
            op[i][1] = 0;
        }
        if (a[i - 1] > a[i] && dp[i][0] > dp[i - 1][0])
        {
    
            dp[i][0] = dp[i - 1][0];
            op[i][0] = 0;
        }
        if (dp[i - 1][1] > a[i] && dp[i][0] > a[i - 1])
        {
    
            dp[i][0] = a[i - 1];
            op[i][0] = 1;
        }
    }
    if (dp[n][1] != -inf)
    {
    
        printf("YES\n");
        for (int i = n, optmp = 1; i >= 1; i--)
        {
    
            opt[i] = optmp;
            optmp = op[i][optmp];
        }
        for (int i = 1; i <= n; i++)
        {
    
            printf("%d ", opt[i] != 1);
        }
    }
    else if (dp[n][0] != inf)
    {
    
        printf("YES\n");
        for (int i = n, optmp = 0; i >= 1; i--)
        {
    
            opt[i] = optmp;
            optmp = op[i][optmp];
        }
        for (int i = 1; i <= n; i++)
        {
    
            printf("%d ", opt[i] != 1);
        }
    }
    else
        printf("NO");
    return 0;
}