Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

PKU 3616 - Milking Time

問題文 : Milking Time

解法 :
dp[N] : 時間Nまでに得られるミルクの最大量, とすると,

dp[N] = max(i = 1 ... M, e[i] ≦ N | dp[s[i]] + v[i] where s[i] = i番目の仕事が始まる時間, e[i] = i番目の仕事が終わる時間)

となる.

ここで, 区間の端以外の時間はいらないので座標圧縮を行っておく. これでO(M^2)で解を求めることができる.


コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int n, m, r;
int s[1024], e[1024], v[1024];
int memo[2048];

int f(int en)
{
	int ret = 0;
	
	if (en == 0) return (0);
	if (memo[en] >= 0) return (memo[en]);
	
	for (int i = 0; i < m; i++){
		if (e[i] <= en){
			ret = max(ret, v[i] + f(s[i]));
		}
	}
	
	return (memo[en] = ret);
}

int main()
{
	map<int, int> conv;
	vector<int> xs;
	scanf("%d %d %d", &n, &m, &r);
	
	n += r;
	
	xs.push_back(0);
	xs.push_back(n);
	for (int i = 0; i < m; i++){
		scanf("%d %d %d", s + i, e + i, v + i);
		e[i] += r;
		xs.push_back(s[i]);
		xs.push_back(e[i]);
	}
	
	sort(xs.begin(), xs.end());
	int idx = 0;
	conv[xs[0]] = idx++;
	for (int i = 1; i < xs.size(); i++) if (xs[i] != xs[i - 1]) conv[xs[i]] = idx++;
	
	for (int i = 0; i < m; i++){
		s[i] = conv[s[i]];
		e[i] = conv[e[i]];
	}
	n = conv[n];
	
	memset(memo, -1, sizeof(memo));
	
	printf("%d\n", f(n));
	
	return (0);
}