題意：

給一個長度為 \(n\) 的入棧序列 \(a\)，問能否產生出棧序列 \(b\)，若可以請給出一種方案。

數據范圍：\(1\le n\le 100\)。

題解：

看到 \(n\) 這么小先想到 dp，接下來就是確定要用什么種類的 dp。

我們從 \(a\) 中的第一個數下手，假設這個數在 \(b\) 中的第 \(k\) 個位置，那么 \(a\) 和 \(b\) 有如下對應關系。

其中：

• \(a\) 中第一個數匹配 \(b\) 中第 \(k\) 個數。
• \(a\) 中第 \(2\to k\) 個數匹配 \(b\) 中第 \(1\to k-1\) 個數。
• \(a\) 中第 \(k+1\to n\) 個數匹配 \(b\) 中第 \(k+1\to n\) 個數。

為什么呢，應為 \(a\) 中一號元素出棧時必定棧只有這一個元素了，所以其前邊的元素都要退棧。自然分成兩個區間了。

接下來就很明顯了，區間 dp。我們設 \(f_{i,j,k}\) 為從 \(a_i\) 和 \(b_j\) 開始匹配 \(k\) 位，是否能匹配上。那么答案就是 \(f_{1,1,n}\)。

考慮遞歸做這個事情，那么要使得 \(f_{i,j,len}\) 為真，需要同時滿足如下條件：

存在一個 \(k\in [1,len]\)，使得其滿足。

• \(a_i=b_{j+k-1}\)
• \(f_{i+1,j,k-1}=1\)
• \(f_{i+k,j+k,len-k}=1\)

考慮時間復雜度：狀態數 \(O(n^3)\) 轉移要枚舉 \(k\) 所以是 \(O(n)\) 的，總時間復雜度是 \(O(n^4)\) 的。

接下來考慮怎么輸出答案，考慮繼續用遞歸，對于一種可行的轉移，我們先把第一位放進去，即為輸出一個 \(S\),然后遞歸第一部分。彈出第一位，也就是輸出一個 \(C\)，接著遞歸第二部分，最后直接 break，不用再找第二個方案了。

code：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=110;
int n,m,k,T,a[N],f[N][N][N],b[N];
int dfs(int x,int y,int l){
	if(l<=0) return 1;
	if(f[x][y][l]!=-1) return f[x][y][l];
	if(l==1){
		if(a[x]==b[y]) f[x][y][l]=1;
		else f[x][y][l]=0;
		return f[x][y][l];
	}int ans=0;
	rep(k,1,l){
		if(a[x]!=b[y+k-1]) continue;
		ans|=(dfs(x+1,y,k-1)&dfs(x+k,y+k,l-k));
	}return f[x][y][l]=ans;
}
void solve(int x,int y,int l){
	if(l<=0) return;
	if(l==1){
		cout<<"S"<<"C";return;
	}rep(k,1,l){
		if(a[x]!=b[y+k-1]) continue;
		if(f[x+1][y][k-1]&f[x+k][y+k][l-k]){
			cout<<"S";solve(x+1,y,k-1);cout<<"C";solve(x+k,y+k,l-k);
			return;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	rep(i,1,n) cin>>a[i];
	rep(i,1,n) cin>>b[i];
    memset(f,-1,sizeof(f));
    if(dfs(1,1,n)){
    	cout<<"YES\n";
    	solve(1,1,n);
	}else cout<<"NO";
	return 0;
}