「JOISC 2020 Day1」建筑装饰 4 （DP）

本文主要是介绍「JOISC 2020 Day1」建筑装饰 4 （DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

• 唯一能自己做出来的一道（呜呜呜）
• 暴力做法是考虑 $dp$ 出 $f_{0/1,x,y}$ 表示最后一个在 $A/B$，$A,B$ 选了 $x,y$ 合不合法，那么发现对于某个特定的 $x+y$，合法的 $x$ 是一个区间，所以记录左右端点 $O(1)$ 转移

#include<bits/stdc++.h>
#define cs const
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;
}

这篇关于「JOISC 2020 Day1」建筑装饰 4 （DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---