动态规划训练22 [Milking Time POJ - 3616 ]

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 ]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。