Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-05-02

BridgeCrossing

| 18:09

問題文

456.12->950.72->985.42 / 1000

わからなくて Editorial を見た。Brute force な方法で解ける。

class BridgeCrossing {
public:
    int minTime(vector <int> times) {
        n = times.size();
        if (n == 1)
            return times[0];
        int best = 9999999;
        vector<bool> side(n, false);
        go(times, 0, n, side, best);
        return best;
    }
private:
    int n;
    void go(const vector<int>& times, const int tm, const int left,
            vector<bool>& side, int& best) {
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!side[i] && !side[j]) {
                    side[i] = side[j] = true;
                    int new_tm = tm + max(times[i],times[j]);
                    if (left == 2) {
                        best = min(best, new_tm);
                    } else {
                        for (int k = 0; k < n; k++) {
                            if (side[k]) {
                                side[k] = false;
                                go(times, new_tm+times[k], left-1,
                                        side, best);
                                side[k] = true;
                            }
                        }
                    }
                    side[i] = side[j] = false;
                }
            }
        }
    }
};