LOJ

分析

设 $dp_{i,0/1,0/1}$ 表示前 $i$ 位,第 $i$ 位选 A / B 时所有满足条件的方案中最多能有多少个 A / B。

转移分四种情况($a_{i-1}\leq a_i$、$a_{i-1}\leq b_i$、$b_{i-1}\leq a_i$、$b_{i-1}\leq b_i$)即可。

考虑从后往前构造方案。设 $sa$ 表示已选的 A 的数量,$sb$ 表示已选的 B 的数量,$pre$ 为前一个数,则当 $sa+dp_{i,0,0}\geq n$ 且 $sb_dp_{i,0,1}\geq n$ 且 $a_i\leq pre$ 时可以选 A。可以选 B 的情况类似。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,a[N],b[N],dp[N][2][2];
char ans[N];

int main() {
    n=read();
    for (int i=1;i<=n<<1;++i) a[i]=read();
    for (int i=1;i<=n<<1;++i) b[i]=read();
    dp[1][0][0]=dp[1][1][1]=1,dp[1][0][1]=dp[1][1][0]=0;
    for (int i=2;i<=n<<1;++i) {
        if (a[i-1]<=a[i]) {
            dp[i][0][0]=max(dp[i][0][0],dp[i-1][0][0]+1);
            dp[i][0][1]=max(dp[i][0][1],dp[i-1][0][1]);
        }
        if (a[i-1]<=b[i]) {
            dp[i][1][0]=max(dp[i][1][0],dp[i-1][0][0]);
            dp[i][1][1]=max(dp[i][1][1],dp[i-1][0][1]+1);
        }
        if (b[i-1]<=a[i]) {
            dp[i][0][0]=max(dp[i][0][0],dp[i-1][1][0]+1);
            dp[i][0][1]=max(dp[i][0][1],dp[i-1][1][1]);
        }
        if (b[i-1]<=b[i]) {
            dp[i][1][0]=max(dp[i][1][0],dp[i-1][1][0]);
            dp[i][1][1]=max(dp[i][1][1],dp[i-1][1][1]+1);
        }
    }
    for (int i=n<<1,sa=0,sb=0,pre=2e9;i;--i) {
        if (a[i]<=pre&&sa+dp[i][0][0]>=n&&sb+dp[i][0][1]>=n)
            pre=a[i],ans[i]='A',++sa;
        else if (b[i]<=pre&&sa+dp[i][1][0]>=n&&sb+dp[i][1][1]>=n)
            pre=b[i],ans[i]='B',++sb;
        else { puts("-1"); return 0; }
    }
    puts(ans+1);
    return 0;
}
最后修改:2020 年 05 月 03 日 09 : 28 PM