POJ 1949 Chores(DAG上的最长路 , DP)

时间:2022-11-09 18:48:52

题意:

给定n项任务, 每项任务的完成用时t和完成每项任务前需要的k项任务, 求把所有任务完成的最短时间,有当前时间多项任务都可完成, 那么可以同时进行。

分析:

这题关键就是每项任务都会有先决条件, 要完成该项任务a必须先完成他的先决条件。

所以对于每个先决条件, 我们构建一条有向边到任务本身, 然后因为要求一个最小值, 按照最长路的方式松弛(dis[v] >= dis[u] + d, u是v的先决条件, d是v的完成时间,我们以边的终点完成时间作为边的权), 遇到没有出度的边记录答案。

方法一:最长路(2016ms)

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#define rep(i,a,b) for(int i = a; i < b; i++)
#define _rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
const int inf = 1e9 + ;
const int maxn = + ;
int n, m;
vector<int> G[maxn];
int d[maxn]; //每条边以终点时间作为权值
int dis[maxn], vis[maxn];
int spfa(){
int ans = -inf;
fill(dis, dis+maxn, -inf); //求最长路
queue<int> q;
dis[] = ;
q.push();//0点入队
vis[] = ;
while(!q.empty()){
int u = q.front();
for(int i = ; i < G[u].size(); i++){
int v = G[u][i]; if(dis[v] < dis[u] + d[v]){
dis[v] = dis[u] + d[v];//每条边以终点时间作为权值
if(G[v].size() == ) {//如果没有出边, 说明它不会对后面有任何影响, 它可能就是答案之一
ans = max(dis[v], ans);//直接更新答案
continue;
}
if(!vis[v]){
vis[v] = ;
q.push(v);
}
}
}
vis[u] = ;
q.pop();
}
return ans;
}
int main()
{
scanf("%d", &n);
_rep(i,,n){
scanf("%d", &d[i]);
int k, v;
scanf("%d", &k);
if(k == ){
G[].push_back(i);//假设有一个0点连向所有入度为0的点, 方便处理
}else{
rep(j,,k){
scanf("%d", &v);
G[v].push_back(i);
}
}
}
printf("%d\n",spfa() );
}

方法二 DP(344ms)

那么我们可以转化一下,假设该项任务有k项先决条件

POJ 1949 Chores(DAG上的最长路 , DP)

dp[i]代表完成该项任务的最早时间, 最后找出最大的dp[i]就是答案。

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#define rep(i,a,b) for(int i = a; i < b; i++)
#define _rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
const int inf = 1e9 + ;
const int maxn = + ;
int worktime[maxn], dp[maxn];
int n, m;
int main()
{
// freopen("1.txt","r", stdin);
scanf("%d", &n);
int ans = -inf;
_rep(i,,n){
scanf("%d", &worktime[i]);//工作时间
int k, v;
scanf("%d", &k);
if(k == ){
dp[i] = worktime[i];
}else{
rep(j,,k){
scanf("%d", &v);
dp[i] = max(dp[i] , dp[v] + worktime[i]);//找出最晚的先决条件
}
}
ans = max(ans, dp[i]);
}
printf("%d\n", ans );
}

POJ 1949 Chores(DAG上的最长路 , DP)的更多相关文章

  1. NYOJ&lowbar;矩形嵌套&lpar;DAG上的最长路 &plus; 经典dp&rpar;

    本题大意:给定多个矩形的长和宽,让你判断最多能有几个矩形可以嵌套在一起,嵌套的条件为长和宽分别都小于另一个矩形的长和宽. 本题思路:其实这道题和之前做过的一道模版题数字三角形很相似,大体思路都一致,这 ...

  2. UVa 10285 最长的滑雪路径(DAG上的最长路)

    https://vjudge.net/problem/UVA-10285 题意: 在一个R*C的整数矩阵上找一条高度严格递减的最长路.起点任意,但每次只能沿着上下左右4个方向之一走一格,并且不能走出矩 ...

  3. Vulnerable Kerbals CodeForces - 772C【拓展欧几里得建图&plus;DAG上求最长路】

    根据拓展欧几里得对于同余方程 $ax+by=c$ ,有解的条件是 $(a,b)|c$. 那么对于构造的序列的数,前一个数 $a$  和后一个数 $b$ ,应该满足 $a*x=b(mod m)$ 即 $ ...

  4. uva103&lpar;最长递增序列,dag上的最长路)

    题目的意思是给定k个盒子,每个盒子的维度有n dimension 问最多有多少个盒子能够依次嵌套 但是这个嵌套的规则有点特殊,两个盒子,D = (d1,d2,...dn) ,E = (e1,e2... ...

  5. HDU 4109 Instrction Arrangement(DAG上的最长路)

    把点编号改成1-N,加一点0,从0点到之前任意入度为0的点之间连一条边权为0的边,求0点到所有点的最长路. SPFA模板留底用 #include <cstdio> #include &lt ...

  6. hdu 1224&lpar;动态规划 DAG上的最长路&rpar;

    Free DIY Tour Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Tot ...

  7. HDU 3249 Test for job (有向无环图上的最长路,DP)

     解题思路: 求有向无环图上的最长路.简单的动态规划 #include <iostream> #include <cstring> #include <cstdlib ...

  8. poj 1949 Chores 最长路

    题目链接 求出最长路..... #include <iostream> #include <vector> #include <cstdio> #include & ...

  9. POJ 1949 Chores (很难想到的dp)

    传送门: http://poj.org/problem?id=1949 Chores Time Limit: 3000MS   Memory Limit: 30000K Total Submissio ...

随机推荐

  1. jquery时间控件datepicker

    配置文件 $("#joinedTime").datepicker({ inline: true, yearRange: "1996:2016", showBut ...

  2. html-webpack-plugin插件的详细介绍和使用

    var webpack = require('webpack'); var HtmlWebpackPlugin = require('html-webpack-plugin'); module.exp ...

  3. 离线网页制作器(beta1&period;0)

    package hhuarongdao; /* *使用方法: 先选择保存路径,然后输入相应的网址, *然后会得到那个网页的离线版的 内容 * */ import java.awt.BorderLayo ...

  4. git 取消&sol;添加 某文件的跟踪

    如果我们不小心将某个文件加入了 git 版本控制,但是突然又不想继续跟踪控制这个文件了,怎么办呢? 使用 git update-index 即可. 不想继续追踪某个文件 git update-inde ...

  5. Spring 4 MVC&plus;Hibernate 4&plus;MySQL&plus;Maven使用注解集成实例

    Spring 4 MVC+Hibernate 4+MySQL+Maven使用注解集成实例 转自:通过注解的方式集成Spring 4 MVC+Hibernate 4+MySQL+Maven,开发项目样例 ...

  6. 使用Libmicrohttpd搭建内嵌(本地)服务器

    Libmicrohttpd简介 GNU Libmicrohttpd是一个用来在项目中内嵌http服务器的C语言库,它具有以下几个非常鲜明的特点: C语言库,小而快. API非常简单,且都是可重入的. ...

  7. Weex开发中的应用小笔记

    内容: 获取输入或其他操作使得值一直改变并在一段不改变的时间后执行下一步操作(输入搜索关键字并执行搜索) https://vuejs.org/v2/guide/computed.html?spm=a2 ...

  8. &period;net拼接json字符串

    { while (reader.Read()) { if (reader.HasRows) { JSONstring += "{"; JSONstring += "\&q ...

  9. TWebBrowser禁止弹出Alert对话框

    以前介绍过通过编写Webbrowser1的OnDocumentComplete事件响应代码可以拦截网页弹出的Alert等对话框,代码如下: procedure TForm1.WebBrowser1Do ...

  10. Lyft Level 5 Challenge 2018 - Final Round &lpar;Open Div&period; 2&rpar; C&period; The Tower is Going Home(思维&plus;双指针)

    https://codeforces.com/contest/1075/problem/C 题意 一个宽为1e9*1e9的矩阵中的左下角,放置一个车(车可以移动到同一行或同一列),放置一些墙,竖的占据 ...