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

題目大意

有個惡劣的電影製片商，習慣性剪接合併電影來讓電影戲份更長。

而我們就是要幫助他XD，他會給我們影片的片段，而我們可以將片段進行合併，條件是片段 A 的 prefix 與片段 B 的 suffix 相同就可以合併，請告訴我們，如何合併可以讓我們的電影最省經費(也就是合併後長度最短)。

參考連結

重點觀念

• 暴力搜尋
• 時間複雜度的確定
• 了解符合題目的規定即可，在題目可以允許的範圍內再好的演算法都一樣

分析

我們先來算算時間複雜度，\(6!=720\)，字串長度也不會超過 10 字元，因此 \(720(10) = 7200\)，怎麼算都綽綽有餘，可以供我們寫暴力的 code XDDD。

心得

嗚嗚，我在耍笨，一開始判斷片段 A 的 prefix 與片段 B 的 suffix 相同就可以合併，應該直接用 string.substr 就好，我還在那邊用迴圈慢慢判斷，花了一大堆時間，最後還寫錯QQQQ。

思考的不夠清楚，腦袋反應不夠好，希望自己可以透過訓練來自己的反應、思考都達到最高水準。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

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