怎样建立自己手机网站,手机app制作视频教程,72建站网如何建设一个药材网站,设计排版软件Milking Time POJ - 3616 说实话这道题目非常简单#xff0c;本质上就是 多段有向图的求最大值问题。稍微变化的地方在于这个的的有向边没有那么明显 #xff0c;而是需要自己去寻找
如果任务i到任务j之间存在有向边的话#xff0c;那么一定有这个关系成立#xff0c;即本质上就是 多段有向图的求最大值问题。稍微变化的地方在于这个的的有向边没有那么明显 而是需要自己去寻找
如果任务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];
vectorint 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);}}}coutdfs(0)endl;return 0;
}
