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

littleKtian · 2025-08-11 18:44:31 · 题解

题意

给定入栈序列 a，询问是否能用一个栈达成出栈序列 b，如果可行则构造方案，序列中元素可重复，n\leq 100。

思路

设 f(i,j,len) 表示从序列 a 中下标为 i、序列 b 中下标为 j 的元素为左端点，长度均为 len 的区间能否使用栈完成要求。

枚举 a_i 在序列 b 的区间 [j,j+len-1] 所匹配的位置，有如下递推公式：

直接 dp 并根据转移过程构造方案即可，时间复杂度 O(n^4)。

#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();
}