| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
附上代码O(mlogm)+O(m^2)#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator