首页 > 代码库 > 【洛谷P2889】Milking Time
【洛谷P2889】Milking Time
很容易想到以结束时间加上R从小到大排序
之后怎样呢?
我们按层考虑,f[i]表示前i个时间段嫩得到的最大价值
每次枚举其之前的状态,如果其ed<当前i的st,那么取max即可
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1010; 6 int n,m,r,f[N]; 7 struct fx{ 8 int st,ed,v; 9 }c[N]; 10 bool cmp(fx a,fx b){ 11 return a.ed<b.ed; 12 } 13 int read(){ 14 int sum=0; 15 char ch=getchar(); 16 while (ch<‘0‘||ch>‘9‘) 17 ch=getchar(); 18 while (ch>=‘0‘&&ch<=‘9‘){ 19 sum=sum*10+ch-‘0‘; 20 ch=getchar(); 21 } 22 return sum; 23 } 24 int main(){ 25 int st,ed,v,ans=0; 26 n=read(); 27 m=read(); 28 r=read(); 29 for (int i=1;i<=m;i++){ 30 c[i].st=read(); 31 c[i].ed=read()+r; 32 c[i].v=read(); 33 } 34 sort(c+1,c+m+1,cmp); 35 for (int i=1;i<=m;i++){ 36 f[i]=c[i].v; 37 for (int j=1;j<i;j++){ 38 if (c[i].st>=c[j].ed) 39 f[i]=max(f[i],f[j]+c[i].v); 40 ans=max(ans,f[i]); 41 } 42 } 43 printf("%d",ans); 44 return 0; 45 }
【洛谷P2889】Milking Time
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。