TOJ 362

TOJ 362

題目

https://toj.tfcis.org/oj/pro/362/

現在有一副撲克牌,分成 $4$ 堆,每一堆都有 $13$ 張牌

現在我們要從 $4$ 個牌堆當中每次選兩張相同的拿出,最後是否有辦法把全部的牌拿完?

想法

我們可以枚舉在每一層當前的 $4$ 張牌當中要取哪兩張,把所有的情況列出,如果能將全部的牌取完就表示有答案,否則沒有

至於要如何知道牌堆中哪張牌是最上方的,我們可以用一個陣列去紀錄 $4$ 個牌堆最上方的牌是牌堆中的第幾張,如此一來要枚舉的時候就只需要改變紀錄的 index 即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//By Koios1143
#include<iostream>
using namespace std;
int arr[4][13];
int top[4];
bool found=false, ans=false;

void DFS(int depth){
if(depth == 26){
ans=true;
found=true;
return;
}
for(int i=0 ; i<4 ; i++){
for(int j=i+1 ; j<4 && !found ; j++){
if(top[i]<13 && top[j]<13 && arr[i][top[i]] == arr[j][top[j]]){
top[i]++;
top[j]++;
DFS(depth+1);
top[i]--;
top[j]--;
}
}
}
}

int main(){
for(int i=0 ; i<4 ; i++){
top[i] = 0;
for(int j=0 ; j<13 ; j++){
cin>>arr[i][j];
}
}
DFS(0);
if(ans){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
return 0;
}

時間複雜度分析

令 $n = 4, m = 13$

輸入時間複雜度為 $O(nm)$

DFS 每層最多有 $4$ 種選擇,總共有 $26$ 層

DFS 時間複雜度為 $O(n^{2m})$

總時間複雜度為 $O(nm + n^{2m})$