首页 > 代码库 > POJ_3616_Milking Time
POJ_3616_Milking Time
1. 题目描述
有m个时间段,每个时间段效率为efficiency,每个时间段过后需要休息r时间,求最大效率和(时间段不重叠)。
2. 代码示例
1 /* 2 Source Code 3 4 Problem: 3616 User: robinho364 5 Memory: 180K Time: 0MS 6 Language: C++ Result: Accepted 7 */ 8 #define _USE_MATH_DEFINES 9 10 #ifdef ONLINE_JUDGE 11 #define FINPUT(file) 0 12 #define FOUTPUT(file) 0 13 #else 14 #define FINPUT(file) freopen(file,"r",stdin) 15 #define FOUTPUT(file) freopen(file,"w",stdout) 16 #endif 17 18 #include <iostream> 19 #include <cstdio> 20 #include <cstring> 21 #include <cstdlib> 22 #include <cmath> 23 #include <ctime> 24 #include <set> 25 #include <stack> 26 #include <string> 27 #include <map> 28 #include <vector> 29 #include <queue> 30 #include <algorithm> 31 #include <functional> 32 33 typedef long long ll; 34 static const int M = 1010; 35 static const int N = 1000010; 36 static const int LEN = 1000010; 37 static const int MAX = 0x7fffffff; 38 static const int MIN = ~MAX; 39 static const double EPS = 1e-7; 40 41 struct cow_t { 42 int start; 43 int end; 44 int efficiency; 45 46 bool operator < (const struct cow_t& t) const { 47 if (end < t.end) { 48 return true; 49 } 50 else { 51 return false; 52 } 53 } 54 }cows[M]; 55 56 void solve(int n, int m, int r) 57 { 58 for (int i = 0; i < m; i++) { 59 scanf("%d%d%d", &cows[i].start, &cows[i].end, &cows[i].efficiency); 60 } 61 62 std::sort(cows, cows + m); 63 64 int pos[M]; 65 66 for (int i = 0; i < m; i++) { 67 int idx = i - 1; 68 while (idx >= 0) { 69 if (cows[idx].end + r <= cows[i].start) { 70 pos[i] = idx; 71 break; 72 } 73 idx--; 74 } 75 if (idx == -1) { 76 pos[i] = -1; 77 } 78 } 79 80 int dp[M]; 81 memset(dp, 0, sizeof(dp)); 82 83 for (int i = 0; i < m; i++) { 84 if (pos[i] == -1) { 85 dp[i] = std::max(cows[i].efficiency, dp[i - 1]); 86 } 87 else { 88 dp[i] = std::max(dp[pos[i]] + cows[i].efficiency, dp[i - 1]); 89 } 90 } 91 92 printf("%d\n", dp[m - 1]); 93 } 94 95 int main() 96 { 97 FINPUT("in.txt"); 98 FOUTPUT("out.txt"); 99 100 int n, m, r; 101 while (scanf("%d%d%d", &n, &m, &r) != EOF) { 102 solve(n, m, r); 103 } 104 return 0; 105 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。