题解 #

我们可以用记忆化 dfs，dp 状态是以下 4 个数：剩余的堆数、最右边三堆里顶端的牌。如果我们最后能剩下一堆的话答案就是 yes。这题也可以用 bfs，状态是 dp 是一样的，可能更好理解。

Code #

#include <bits/stdc++.h>
using namespace std;
 
const int N=60;
string s[N];
int dp[N][N][N][N];
bool dfs(int n,int i,int j,int k){
	if(n==0) return true;
	int& d=dp[n][i][j][k];
	if(dp[n][i][j][k]) return dp[n][i][j][k]==1?true:false;
	if(s[i][0]==s[j][0]||s[i][1]==s[j][1]){
		if(dfs(n-1,i,k,n-3)){
			return d=1;
		}
	}
	if(n>=3&&(s[i][0]==s[n-3][0]||s[i][1]==s[n-3][1])){
		if(dfs(n-1,j,k,i)){
			return d=1;
		}
	}
	d=-1;
	return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;
	cin>>n;
	forn(i,n) cin>>s[i];
	cout<<(dfs(n-1,n-1,n-2,n-3)?"YES":"NO");
    return 0;
}

Codeforces 208B - Solitaire 题解

题解 #

Code #