読者です 読者をやめる 読者になる 読者になる

POJ 3616 Miliking Time

http://poj.org/problem?id=3616
 引き続き蟻本の練習問題を解いています。
 簡単なのでメモ程度に……。
 休憩or作業が終わった時間を持ってdpします。
愚直解はこんなん

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

const int INF = 1.0e9;
typedef pair<int, int> pint;
typedef pair<pint, int> tup;
int dp[1000001];
int main() {
    int N, M, R; scanf("%d%d%d", &N, &M, &R);
    vector<tup> Q(M);
    rep(i, M) {
        int st, et, ef; scanf("%d%d%d", &st, &et, &ef);
        Q[i] = tup(pint(st, et), ef);
    }
    sort(Q.begin(), Q.end());
    rep(i, M) {
        int st = Q[i].first.first, et = Q[i].first.second, ef = Q[i].second;
        for(int t = 0; t + R < st; ++t)
          dp[et] = max(dp[et], dp[t] + ef);
    }
    printf("%d\n", *max_element(dp, dp + N + 1));
    return 0;
}

で、mapで速くすると

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
const int INF = 1.0e9;
typedef pair<int, int> pint;
typedef pair<pint, int> tup;
int main() {
    int N, M, R; scanf("%d%d%d", &N, &M, &R);
    vector<tup> Q(M);
    rep(i, M) {
        int st, et, ef; scanf("%d%d%d", &st, &et, &ef);
        Q[i] = tup(pint(st, et), ef);
    }
    sort(Q.begin(), Q.end());
    map<int, int> dp; dp[0] = 0;
    rep(i, M) {
        int st = Q[i].first.first, et = Q[i].first.second, ef = Q[i].second;
        int key1 = st * -1, key2 = (et + R) * -1;
        map<int, int>::iterator it = dp.lower_bound(key1);
        for(; it != dp.end(); ++it)
          dp[key2] = max(dp[key2], it->second + ef);
    }
    int ans = 0;
    for(map<int, int>::iterator it = dp.begin(); it != dp.end(); ++it)
      ans = max(ans, it->second);
    printf("%d\n", ans);
    return 0;
}

こんな感じ。
 別にmap使わなくてもクエリ番号を鍵にすれば大丈夫そうですけど、こっちの方がわかりやすいかも?
 それにしてもPOJはC++11以降が使えないので辛いですね。

for(map<int, int>::iterator it = dp.begin(); it != dp.end(); ++it)

とか

typedef pair<int, int> pint;
typedef pair<pint, int> tup;
int st = Q[i].first.first, et = Q[i].first.second, ef = Q[i].second;

とか書いてると悲しくなります。