POJ-3616 : Milking Time

問題概要

重み付き区間スケジューリング問題。

解法

DP。

acceptされたコード

座標圧縮したらもっと速くなるのは知ってる。座標圧縮しないとき、g++だとTLEしたけどc++だと通った。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = (int)(1e6);

int N, M, R;
vector< pair<int,int> > rs[MAX_N];
bool on[MAX_N];
int dp[MAX_N + 1];

void init(){
	scanf("%d%d%d", &N, &M, &R);
	for(int i=0; i<M; i++){
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		rs[x].push_back(make_pair(min(y+R, N), z));
		on[x] = true;
	}
}

int solve(){
	for(int i=0; i<N; i++){
		dp[i+1] = max(dp[i+1], dp[i]);
		if(on[i]){
			for(int j=0; j<(int)rs[i].size(); j++){
				dp[rs[i][j].first] = max(dp[rs[i][j].first], dp[i] + rs[i][j].second);
			}
		}
	}

	return dp[N];
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}