POJ 3616 Milking Time G++动态规划 背

#include <iostream> #include <vector> #include <algorithm> using namespace std; //抄博友程序 动态规划 背 struct nod{ int st; int en; int zhi; }; bool cmp(nod a,nod b) { return a.st<b.st; } int dp[1009]; int main() { int N,M,R; cin>>N>>M>>R; vector<nod> ve; for(int i=0;i<M;i++) { nod t; cin>>t.st>>t.en>>t.zhi; t.en=t.en+R; if((t.en-R)<=N) { ve.push_back(t); } } sort(ve.begin(),ve.end(),cmp); /* for(int i=0;i<ve.size();i++) { cout<<ve[i].st<<" "<<ve[i].en<<" "<<ve[i].zhi<<endl; }*/ int jg=0; for(int i=0;i<ve.size();i++) { dp[i]=ve[i].zhi;//dp[i]表示的是 在第i个时间段挤奶的情况下 第i个时间段的最大值 for(int j=0;j<i;j++) { if(ve[j].en<=ve[i].st) { dp[i]=max(dp[i],dp[j]+ve[i].zhi); jg=max(jg,dp[i]);//抄博友程序 } } } cout<<jg<<endl; return 0; }