「JOISC 2020 Day1」建築裝飾 4 （DP）

• 唯一能自己做出來的一道（嗚嗚嗚）
• 暴力做法是考慮出表示最後一個在，選了合不合法，那麼發現對于某個特定的，合法的是一個區間，是以記錄左右端點

#include<bits/stdc++.h>
#define
using namespace std;
cs int N = 1e6 + 50;
int read(){
  int cnt=0, f=1; char ch=0;
  while(!isdigit(ch)){ ch=getchar(); if(ch=='-') f=-1; }
  while(isdigit(ch)) cnt=cnt*10+(ch-'0'), ch=getchar();
  return cnt*f;
}
int n, a[N], b[N];
int l1[N], r1[N], l2[N], r2[N];
void work(int typ, int u, int c){
  if(u==0) return; assert(c>=0);
  if(typ==0){
    if(l1[u-1]<=c-1&&c-1<=r1[u-1]&&a[u-1]<=a[u]) work(0,u-1,c-1);
    else work(1,u-1,c-1); cout<<"A";
  }
  if(typ==1){
    if(l1[u-1]<=c&&c<=r1[u-1]&&a[u-1]<=b[u]) work(0,u-1,c);
    else work(1,u-1,c); cout<<"B";
  }
}
int main(){
  n=read();
  for(int i=1; i<=n+n; i++) a[i]=read();
  for(int i=1; i<=n+n; i++) b[i]=read();
  memset(r1,-1,sizeof(r1));
  memset(r2,-1,sizeof(r2));
  memset(l1,0x3f,sizeof(l1));
  memset(l2,0x3f,sizeof(l2));
  l1[1]=1; r1[1]=1; l2[1]=0; r2[1]=0;
  for(int i=2; i<=n+n; i++){
    if(a[i]>=a[i-1]) l1[i]=min(l1[i-1]+1,l1[i]), r1[i]=max(r1[i],r1[i-1]+1);
    if(a[i]>=b[i-1]) l1[i]=min(l2[i-1]+1,l1[i]), r1[i]=max(r1[i],r2[i-1]+1);
    if(b[i]>=a[i-1]) l2[i]=min(l2[i],l1[i-1]), r2[i]=max(r2[i],r1[i-1]);
    if(b[i]>=b[i-1]) l2[i]=min(l2[i],l2[i-1]), r2[i]=max(r2[i],r2[i-1]);
    if(l1[i]>r1[i]&&l2[i]>r2[i]){ puts("-1"); return 0; }
  } 
  if(l1[n+n]<=n&&n<=r1[n+n]){ work(0,n+n,n); return 0; } 
  if(l2[n+n]<=n&&n<=r2[n+n]){ work(1,n+n,n); return 0; }
  puts("-1"); return 0;
}