Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

附上代码O(mlogm)+O(m^2)

Posted by scissorsy at 2016-01-19 00:55:01 on Problem 3616
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cstring>
const int MAX_M = 1000;
using namespace std;
int main() {
	//dp[i] = max(dp[x]) + e[i];//dp[i] : The maximum yield if milking end with i-th interval 
	/*def*/
	int N, M, R, dp[MAX_M], res;
	pair<pair<int, int>, int> intervals[MAX_M];
	
	/*input*/
	scanf("%d%d%d",&N, &M, &R);
	for(int i = 0;i<M;i++)
		scanf("%d%d%d", &intervals[i].first.first, &intervals[i].first.second, &intervals[i].second);
		
	/*init*/
	sort(intervals, intervals+M);
	memset(dp, 0, sizeof(dp));
	res = 0;
	/*dp*/
	for(int i = 0;i<M;i++){
		for(int j = 0;j<M;j++)
			if(intervals[j].first.second + R <= intervals[i].first.first)
				dp[i] = max(dp[j], dp[i]);
		dp[i] += intervals[i].second;
		res = max(dp[i], res);
	}
	printf("%d\n", res);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator