UVa11753 - Creating Palindrome(DFS )

題目大意

你來幫幫 ICPC 的忙，ICPC 會給你一組數列，與一個數字 k，請你告訴 ICPC 要在這數列中至少要插入幾個數字才可以成為迴文數列，如果插入的次數大於 k 輸出 too difficult，如果不需要插入輸出 too easy，除此之外，輸出你插入的次數。

題目連結

重點觀念

• 思考這題是 DFS 的應用
• 了解這題貪心不一定會是好解法

分析

我們可以先透過數列進行簡單分析，定義數列的左邊界指針為 L、右邊界指針為 R，數列為 num

• 如果 \(num[L] == num[R] \) 就 L-1、R-1。
• 如果 \(num[L] != num[R] \)，我們可以怎麼做?
  • 用貪心解嗎？
    你可能會這麼覺得，我就只要判斷下一個數字有沒有等於 \(num[L] \) or \(num[R] \) 就好了，可是那假如下下個數字等於 \(num[L] \) or \(num[R] \) 呢？
  • 用 DFS 嗎？
    效率很差，但是看看這邊的 K 只有 20，也就是說 DFS 只要跑到 20 就好，那並不會讓 DFS 過長。
  • 用 DP 嗎？
    不妥，因為 DP 時當字串過長時，會有大量座標浪費在解不出來的情況，例如：(1,2000) = 1999，那我們就有很多時間浪費在跑 y = 1~2000 的情況

主要是透過 DFS 去找出最適合的組合，當 \(num[L] != num[R] \)，就延伸出兩種 DFS，L+1, R、L,R-1。

參考連結

Uva11753 - Creating Palindrome by txya900619

心得

這題算是輕鬆題目，寫的算快。希望以後都能能輕鬆寫完啦。

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 0x3f3f3f
using namespace std;
int t, n, k, kase=0;
vector<int> num;
int ans_d; //最小的插入次數

void dfs(int L, int R, int d){ //DFS 找出最好排列組合
    //cout << "num L R " << num[L] << ' ' << num[R] << '\n';
    if(L >= R ){ //左指針與右指針相遇就 return，注意：奇數迴文則不需要在意最中間的數值
        ans_d = min(d, ans_d); //找出最小插入次數
        return;
    }
    //大於題目最大要求的 k 時，直接 return，並將這次的 d 設定為 k+1，才能讓最後輸出時可以輸出 too difficult
    if(d > k){ 
        ans_d = min(k+1, ans_d); 
        return;
    }
    if(num[L] == num[R]) dfs(L+1, R-1, d); //一樣，左右指針 -1
    if(num[L] != num[R]){ //不一樣時
        dfs(L+1, R, d+1); //讓左指針 +1，步數+1
        dfs(L, R-1, d+1); //讓右指針 -1，步數+1
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    cin >> t;
    while(t--){ 
        num.clear(); //清除數列，以免被先前資料影響
        cin >> n >> k;
        int temp;
        for(int i = 0; i < n; i++){ //讀資料
            cin >> temp;
            num.push_back(temp);
        }

        ans_d = MAXN;
        dfs(0, num.size()-1, 0); //進行 DFS

        //cout << "ans_d " << ans_d << '\n';
        //判斷是哪種狀態，太簡單、太難，還是輸出插入次數
        cout << "Case " << ++kase << ": ";
        if(ans_d == 0) cout << "Too easy\n";
        else if(ans_d <= k) cout << ans_d << "\n";
        else if(ans_d > k) cout << "Too difficult\n";
    }


    return 0;
}