UVa12249 - Overlapping Scenes (數論 Math theorm、暴力搜尋 Brute force)

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 15;
int t, n, kase=0;
string scenes[MAXN]; //儲存題目的電影片段
int used[MAXN]; //判斷電影片段是否被使用過
int ans; //合併最短長度

void dfs(string merge_scene, int count_recursive){ //排列組合
    if(count_recursive >= n){ //如果所有的電影片段都被用過
        //cout << merge_scene << '\n';
        int len = merge_scene.length(); 
        ans = min(len, ans); //選出最小的字串長度
        return;
    }
    for(int i = 0; i < n; i++){ //排列組合
        if(used[i]) continue; //之前有被用過的，就不用

        int k = min(scenes[i].length(), merge_scene.length()); 
        //從兩個字串中選出最小長度，因為他們的合併片段**最大**只能到此長度
        while(k > 0){ //不斷嘗試
            string substrA = merge_scene.substr(merge_scene.length()-k,k); //擷取字串
            string substrB = scenes[i].substr(0,k); //擷取字串
            if(substrA == substrB){ //只要找到可以合併的，就退出。
            //由於 k 從最大開始，因此只要**第一個** substrA == substrB 就可以退出
                //cout << substrA << ' ' << substrB << '\n';
                break;
            }
            k--;
        }
        used[i] = 1; //表示此電影片段已被用過
        string temp = merge_scene + scenes[i].substr(k, scenes[i].length()-k); //indice 0
        //temp 是合併字串
        dfs(temp, count_recursive+1); //向下排列組合
        used[i] = 0; //回到當前遞迴，所以當前電影片段不再被使用
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0; i < n; i++){ //輸入資料
            cin >> scenes[i];
            used[i] = 0;
        }
        ans = 0x3f3f3f; //表示長度一開始 infinite
        dfs("",0);
        cout << "Case " << ++kase << ": " << ans << '\n'; //輸出答案
    }
    return 0;
}