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