Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2012-04-22

PKU3333 Co-workers from hell

01:54

嘘解法で通る.正当な方法あるのかこれ…….

/*
 * 最長経路問題なので基本的にはDFS.
 * ただ単純にDFSしても通らないので,前に進むtrickのうち
 * 普通に進んだほうが長くなるものは使わないようにする.
 *
 * 普通に考えて,これだと
 * 1 10 2
 * 1 10 3
 *   :
 *   :
 * 1 10 100
 * 1 10 1
 * みたいなケースで死ぬのだが,なぜか通る.
 * 参照: http://www.cppblog.com/bnugong/archive/2008/07/16/56309.html
 */
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>

using namespace std;

struct Tag {
    int normal, trick, next;

    Tag() {}
    Tag(int n, int t, int ne) : normal(n), trick(t), next(ne) {}
};

int ans = 0;
void dfs(const vector<Tag> &chambers, int pos, vector<int> &used, int acc) {
    if(pos == (int)chambers.size()) {
        ans = max(ans, acc);
        return;
    }

    if(!used[pos]) {
        used[pos] = 1;
        dfs(chambers, chambers[pos].next, used, acc+chambers[pos].trick);
        used[pos] = 0;
        if(chambers[pos].next <= pos) return;
    }
    dfs(chambers, pos+1, used, acc+chambers[pos].normal);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int N;
        cin >> N;
        vector<Tag> chambers;
        for(int i = 0; i < N; ++i) {
            int a, b, c;
            cin >> a >> b >> c;
            --c;
            chambers.push_back(Tag(a, b, c));
        }

        vector<int> used(N, 0);
        ans = 0;
        for(int i = 0; i < N; ++i) {
            if(chambers[i].next > i) {
                int cost = 0;
                for(int j = i; j < chambers[i].next; ++j) {
                    cost += chambers[j].normal;
                }
                if(cost >= chambers[i].trick) {
                    used[i] = 1;
                }
            }
        }
        dfs(chambers, 0, used, 0);
        cout << ans << endl;
    }

    return 0;
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/osa_k/20120422
リンク元
 |