Milking Time

? POJ - 3616?

說實話這道題目非常簡單，本質上就是 多段有向圖的求最大值問題。稍微變化的地方在于這個的的有向邊沒有那么明顯 ，而是需要自己去尋找

如果任務i到任務j之間存在有向邊的話，那么一定有這個關系成立，即：i.endtime + R <= j.endtime

對所有滿足上面條件的任務之間建立有向邊，然后dfs記憶化搜索ok

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <vector> using namespace std; const int MAX = 1005; int ishead[MAX]; vector<int> G[MAX]; int N,M,R; int s[MAX]; int e[MAX]; int v[MAX]; int dp[MAX]; int dfs(int u){if(dp[u]) return dp[u];dp[u] = v[u];for(int i = 0;i < G[u].size();i++){int vs = G[u][i];dp[u] = max(dp[u],dfs(vs) + v[u]);}return dp[u]; } int main(){scanf("%d%d%d",&N,&M,&R);for(int i = 1;i <= M;i++){int ts,te,tv;scanf("%d%d%d",&ts,&te,&tv);s[i] = ts,e[i] = te,v[i] = tv;}s[0] = e[0] = -R; v[0] = 0;for(int i = 0;i <= M;i++){for(int j = 1;j <= M;j++){if(i == j) continue;if(e[i] + R <= s[j]){G[i].push_back(j);}}}cout<<dfs(0)<<endl;return 0; }

總結

以上是生活随笔為你收集整理的动态规划训练22 [Milking Time POJ - 3616 ]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。