题解：P13586 [NWRRC 2023] First Solved, Last Coded

题意

给定入栈序列

a

，询问是否能用一个栈达成出栈序列

b

，如果可行则构造方案，序列中元素可重复，

n\leq 100

。

思路

设

f(i,j,len)

表示从序列

a

中下标为

i

、序列

b

中下标为

j

的元素为左端点，长度均为

len

的区间能否使用栈完成要求。

枚举

a_i

在序列

b

的区间

[j,j+len-1]

所匹配的位置，有如下递推公式：

f(i,j,len)=\bigvee_{k=j}^{j+len-1}([a_i=b_k]\wedge f(i+1,j,k-j)\wedge f(i+k-j+1,k+1,j+len-1-k))

直接 dp 并根据转移过程构造方案即可，时间复杂度

O(n^4)

。

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[105],b[105],f[105][105][105];
int dp(int l1,int l2,int len){
	if(len<=0)return 1;
	if(f[l1][l2][len]!=-1)return f[l1][l2][len];
	int r1=l1+len-1,r2=l2+len-1;
	if(r1>n||r2>n)return f[l1][l2][len]=0;
	if(len==1)return f[l1][l2][len]=a[l1]==b[l2]?1:0;
	int ans=0;
	for(int i=l2;i<=r2;i++){
		int lans=(a[l1]==b[i]?1:0)&dp(l1+1,l2,i-l2)&dp(l1+i-l2+1,i+1,r2-i);
		ans|=lans;
	}
	return f[l1][l2][len]=ans;
}
void print(int l1,int l2,int len){
	if(len<=0)return;
	if(len==1){
		cout<<'S'<<'C';
		return;
	}
	int r1=l1+len-1,r2=l2+len-1;
	for(int i=l2;i<=r2;i++){
		int lans=(a[l1]==b[i]?1:0)&dp(l1+1,l2,i-l2)&dp(l1+i-l2+1,i+1,r2-i);
		if(lans==1){
			cout<<'S';
			print(l1+1,l2,i-l2);
			cout<<'C';
			print(l1+i-l2+1,i+1,r2-i);
			return;
		}
	}
}
void work(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)f[i][j][k]=-1;
	int ans=dp(1,1,n);
	if(ans==1){
		cout<<"YES\n";
		print(1,1,n);
	}else cout<<"NO";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T=1;
	while(T--)work();
}

题解：P13586 [NWRRC 2023] First Solved, Last Coded

文章操作

题意

思路

相关推荐

评论

题解：P13586 [NWRRC 2023] First Solved, Last Coded