Uva11753 - Creating Palindrome

題目大意

大概就是要找到一個序列最少需要插入幾個數字會是回文，如果原本就是回文輸出 Too esay，如果超過 k 輸出 Too difficult，如果都沒有輸出答案。

重點觀念

分析

• 直接 dfs 然後邊界要用好不然會 tle

程式題目碼

#include <algorithm>
#include <iostream>
using namespace std;

int n, k;
int a[10005];
int ans = INT32_MAX;

void dfs(int l, int r, int cnt) {
    if (l >= r || cnt >= ans || cnt > k) {
        if (cnt < ans) {
            ans = cnt;
        }
        return;
    }

    if (a[l] == a[r]) {
        dfs(l + 1, r - 1, cnt);
    } else {
        dfs(l + 1, r, cnt + 1);
        dfs(l, r - 1, cnt + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;

    for (int i = 1; i <= t; i++) {
        ans = INT32_MAX;
        cin >> n >> k;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }

        dfs(0, n - 1, 0);

        cout << "Case " << i << ": ";
        if (ans == 0) {
            cout << "Too easy";
        } else if (ans > k) {
            cout << "Too difficult";
        } else {
            cout << ans;
        }
        cout << endl;
    }

    return 0;
}