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;
とか書いてると悲しくなります。