【dp】Milking Time POJ - 3616

xiaoxiao2021-02-28  86

/* 基础dp R - Milking Time 题意: 在N小时内,有M个可以得到的牛奶,在相应的时间段得到相应的牛奶,在一时间只能处理一个, 而且每次得到后要休息R时间,才能进行下一次。问最大能得到的牛奶总量。 题解:首先每个时间段都在N内,那其实就是求在m个选择几个得到最大。 先将结束的时间均加上R,就能处理R的问题了吧。 然后就类似叠塔问题了,排序+LIS吧 */ #include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> using namespace std; const int N = 1010; int n,m,r; struct asd { int begin; int end; int val; }a[N]; bool cmp(asd a, asd b) { return a.begin < b.begin; } int dp[N]; int main() { while(cin>>n>>m>>r) { memset(dp,0,sizeof(dp)); int be,en,va; for(int i = 0; i < m; i++) { cin>>be>>en>>va; a[i].begin = be; a[i].end = en+r; a[i].val = va; } sort(a,a+m,cmp); int ans = 0; for(int i = 0; i < m; i++) { dp[i] = a[i].val; for(int j = i-1; j >= 0; j--) { if(a[i].begin >= a[j].end) dp[i] = max(dp[i],a[i].val+dp[j]); } ans = max(ans,dp[i]); } cout << ans << endl; } return 0; }
转载请注明原文地址: https://www.6miu.com/read-56826.html

最新回复(0)