首页 > 代码库 > poj 3616 Milking Time dp
poj 3616 Milking Time dp
题目大意是一个奶牛可以在一些时间区间产奶，每个区间的产奶量已知，每次产完奶都要休息一下，问最大产奶量。
dp方程类似最长上升子序列的n2算法，dp[i]表示以第i个区间结尾最多能产生多少奶。
则dp[i] = max(dp[j] + e[i].z)。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int dp[1010];struct node{ int x,y,z;}e[1010];bool cmp(node a,node b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x;}int main(){ int n,m,r,ans; while(scanf("%d%d%d",&n,&m,&r)!=EOF) { int i,j; for(i=0;i<m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); sort(e,e+m,cmp); ans=0; for(i=0;i<m;i++) dp[i]=e[i].z; for(i=0;i<m;i++) { for(j=0;j<i;j++) if(e[j].y+r<=e[i].x) dp[i]=max(dp[i],dp[j]+e[i].z); ans=max(ans,dp[i]); } printf("%d\n",ans); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。