首页 > 代码库 > poj3616 Milking Time
poj3616 Milking Time
思路:
dp。
实现:
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 typedef long long ll; 6 ll n,m,r; 7 struct node 8 { 9 ll start; 10 ll end; 11 ll p; 12 }; 13 node a[1005]; 14 ll dp[1005]; 15 bool cmp(const node & a,const node & b) 16 { 17 if(a.start != b.start) 18 { 19 return a.start < b.start; 20 } 21 return a.end < b.end; 22 } 23 ll solve() 24 { 25 for(int i = 0;i < m;i ++) 26 { 27 dp[i] = a[i].p; 28 for(int j = 0;j < i;j ++) 29 { 30 if(a[j].end <= a[i].start) 31 dp[i] = max(dp[i], dp[j] + a[i].p); 32 } 33 } 34 ll maxn = 0; 35 for(int i = 0;i < m;i ++) 36 maxn = max(maxn, dp[i]); 37 return maxn; 38 } 39 int main() 40 { 41 cin >> n >> m >> r; 42 for(int i = 0;i < m;i ++) 43 { 44 scanf("%lld%lld%lld",&a[i].start,&a[i].end,&a[i].p); 45 a[i].end += r; 46 } 47 sort(a, a + m,cmp); 48 cout << solve() << endl; 49 return 0; 50 }
poj3616 Milking Time
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。