题目链接

GCJ 2009 R1C C. Bribe the Prisoners

思路

官方提示

时间复杂度

$$ O(Q^2log(Q)) $$

代码

#include <cstdio>
#include <map>
#include <iostream>

using namespace std;

map<pair<int, int>, int> mmp;

const int MAXN = 110;

int n, m;
int a[MAXN];

int gao(int l, int r) {
    pair<int, int> cur = {l, r};
    if (mmp.count(cur) != 0) {
        return mmp[cur];
    }
    int res = 0;
    for (int i = 1; i <= m; i++) {
        int x = a[i];
        if (l <= x && x <= r) {
            int tmp = (r - l) + gao(l, x - 1) + gao(x + 1, r);
            if (res == 0 || tmp < res) {
                res = tmp;
            }
        }
    }
    return mmp[cur] = res;
}

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    for (int kase = 1; kase <= T; kase++) {
        mmp.clear();
        scanf("%d%d", &n, &m);// don't forget &
        for (int i = 1; i <= m; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        printf("Case #%d: %d\n", kase, gao(1, n));
    }
    return 0;
}