题解 - 「JOISC 2020 Day1」建筑装饰 4

$\mathrm{ 「JOISC \ 2020 \ Day1」}$「JOISC 2020 Day1」 建筑装饰4 题解

题目意思

「JOISC 2020 Day1」建筑装饰 4

$\mathrm{Sol}$Sol

$\mathrm{Sol1}$Sol1

• 对于$O(n^2)$O(n2)还是比较容易的。我们考虑设$f_{i,j,A/B}$fi,j,A/B​ 表示对于前$i$i个数有几个选$A$A，现在选$A/B$A/B末尾最小值为多少，大力转移即可。
• 期望得分$11ptc$11ptc，$JOI$JOI的部分分怎么就这么奇怪讷?

$\mathrm{Sol2}$Sol2

• 考虑优化$DP$DP的状态，我们设$f_{i,A/B,A/B}$fi,A/B,A/B​表示到第$i$i位选择$A/B$A/B为了最大化$A/B$A/B，此时最多能选多少$A/B$A/B，转移如下：
  • 对于$a_{i-1}\leq a_i$ai−1​≤ai​，我们考虑都选，那么就有
    • $f_{i,A,A}=\max(f_{i-1,A,A}+1)$fi,A,A​=max(fi−1,A,A​+1)
    • $f_{i,A,B}=\max(f_{i-1,A,B})$fi,A,B​=max(fi−1,A,B​)
  • 对于$a_{i-1}\leq b_i$ai−1​≤bi​，我们考虑都选，那么就有
    • $f_{i,A,A}=\max(f_{i-1,B,A}+1)$fi,A,A​=max(fi−1,B,A​+1)
    • $f_{i,A,B}=\max(f_{i-1,B,B})$fi,A,B​=max(fi−1,B,B​)
  • 对于$b_{i-1}\leq b_i$bi−1​≤bi​，我们考虑都选，那么就有
    • $f_{i,B,B}=\max(f_{i-1,B,B}+1)$fi,B,B​=max(fi−1,B,B​+1)
    • $f_{i,B,A}=\max(f_{i-1,B,A})$fi,B,A​=max(fi−1,B,A​)
  • 对于$b_{i-1}\leq a_i$bi−1​≤ai​，我们考虑都选，那么就有
    • $f_{i,B,B}=\max(f_{i-1,A,B}+1)$fi,B,B​=max(fi−1,A,B​+1)
    • $f_{i,B,A}=\max(f_{i-1,A,A})$fi,B,A​=max(fi−1,A,A​)
• 然后我们考虑如何统计答案。如果对于一个位置$i$i，当前选了$a$a个$A$A，$b$b个$B$B，那么如果$n\leq f_{i,A,A}+a$n≤fi,A,A​+a并且$n\leq f_{i,A,B}+b$n≤fi,A,B​+b那么这个位置是可以放$A$A的，对于$B$B同理。
• 最后我们需要倒序枚举，保证$A,B$A,B个数大于等于$n$n个

$\mathrm{Code}$Code

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

inline int read() 
{
	int sum=0,ff=1;
	char ch=getchar();
	while(!isdigit(ch)) 
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

const int N=1e6+5;
const int A=0,B=1;

int n,m,f[N][2][2],a[N],b[N],ans[N];

int main() 
{
	n=read();
	m=n*2;
	for ( int i=1; i<=m; i++ ) a[i]=read();
	for ( int i=1; i<=m; i++ ) b[i]=read();
	memset(f,128,sizeof f);
	f[1][A][A]=1;
	f[1][B][B]=1;
	f[1][A][B]=f[1][B][A]=0;
	for ( int i=2; i<=m; i++ ) 
	{
		if(a[i]>=a[i-1]) 
		{
			f[i][A][A]=max(f[i-1][A][A]+1,f[i][A][A]);
			f[i][A][B]=max(f[i][A][B],f[i-1][A][B]);
		}
		if(a[i]>=b[i-1]) 
		{
			f[i][A][A]=max(f[i][A][A],f[i-1][B][A]+1);
			f[i][A][B]=max(f[i][A][B],f[i-1][B][B]);
		}
		if(b[i]>=b[i-1])
		{
			f[i][B][B]=max(f[i][B][B],f[i-1][B][B]+1);
			f[i][B][A]=max(f[i][B][A],f[i-1][B][A]);
		}
		if(b[i]>=a[i-1])
		{
			f[i][B][B]=max(f[i][B][B],f[i-1][A][B]+1);
			f[i][B][A]=max(f[i][B][A],f[i-1][A][A]);
		}
	}
	int gsA=0,gsB=0,LA=1e9+1;
	for ( int i=m;i;i-- ) 
	{
		if(gsA+f[i][A][A]>=n&&gsB+f[i][A][B]>=n&&a[i]<=LA) 
		{
			ans[i]=A;
			LA=a[i];
			gsA++;
		}
		else 
			if(gsA+f[i][B][A]>=n&&gsB+f[i][B][B]>=n&&b[i]<=LA) 
			{
				ans[i]=B;
				LA=b[i];
				gsB++;
			}
			else return printf("-1\n"),0;
	}
	for ( int i=1;i<=m;i++ ) putchar(ans[i]+'A');
	return 0;
}
/*
6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78
*/