HDU 4109 Instrction Arrangement（DAG上的最长路径）记忆化搜索

你的名字 2024-02-17 19:17 49阅读 0赞

题意：给n条指令，0到n-1，有些指令之间有依赖关系（x到y需要一段安全时间z），除这种关系之外所有指令可以同时进行；求CPU执行的最少时间。

思路：就是求DAG上的最长路径（dp求解），记忆化搜索，防止超时。

AC代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=10000+10;
    int g[1100][1100];
    int n,m;
    struct node{
    	int x,y;
    	node(int x=0,int y=0):x(x),y(y){}
    }nt[maxn];
    int t[1100][1100];
    int d[1100];    
    int dp(int i){
    	int&ans=d[i];
    	if(ans>0)return ans;
    	ans=1;      //如果是这条路上的最后一条指令，直接返回（if语句不满足条件了，花费时间为1） 
    	for(int j=0;j<n;j++){
    		if(g[i][j])ans=max(ans,dp(j)+t[i][j]);
    	}
    	return ans;
    }
    int main(){
    	while(scanf("%d%d",&n,&m)==2){
    		memset(d,0,sizeof(d));
    		memset(g,0,sizeof(g));
    		memset(t,0,sizeof(t));
    		for(int i=0;i<m;i++){
    			int a,b,c;
    			scanf("%d%d%d",&a,&b,&c);
    		    nt[i]=node(a,b);
    		    g[a][b]=1;
    		    t[a][b]=c;
    			}
    	   int ans=-1;
    	   for(int i=0;i<n;i++){
    	   	ans=max(ans,dp(i));
    	   }
    	   printf("%d\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，49人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1181（记忆化搜索）

呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒

我不是女神ヾ/ 2024年02月17日 19:43/ 0 赞/ 87 阅读

相关 HDU 4109 Instrction Arrangement（DAG上的最长路径）记忆化搜索

题意：给n条指令，0到n-1，有些指令之间有依赖关系（x到y需要一段安全时间z），除这种关系之外所有指令可以同时进行；求CPU执行的最少时间。思路：就是求DAG上的最长路径

你的名字/ 2024年02月17日 19:17/ 0 赞/ 50 阅读

相关 hdu 1078 （dp记忆化搜索）

题意：有一个n\n的方格，每个格子有一个价值，经过这个格子就可以得到这个价值，每次可以横着或者竖着一步最多走K格，并且每次走的格子要比上一个格子的价值大，问现在从位置(1,1)

清疚/ 2022年08月20日 13:26/ 0 赞/ 200 阅读

相关 HDU-1142-最短路+记忆化搜索

A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 655

旧城等待，/ 2022年07月11日 13:01/ 0 赞/ 184 阅读

相关 HDU 4109 Instrction Arrangement（拓扑排序+bfs）

Ali has taken the Computer Organization and Architecture course this term. He learned th

叁歲伎倆/ 2022年06月11日 05:45/ 0 赞/ 126 阅读

相关【数位DP+记忆化搜索】不要62 HDU - 2089

Think: 1知识点：数位DP+记忆化搜索 2思考：（1）：注意符合题意条件的判断（当ok为true的状态） 3题意：输入一个区间，判断这个区间内不含4且不

╰半橙微兮°/ 2022年06月08日 09:59/ 0 赞/ 230 阅读

相关 HDU2571(记忆化搜索)

<table style="font-family:'Times New Roman';"> <tbody> <tr> <td align="center">

绝地灬酷狼/ 2022年05月29日 00:15/ 0 赞/ 192 阅读

相关 HDU5456 记忆化搜索

[传送门][Link 1] 题意：给你n个火柴，能拼成几个A-B=C的等式思路：可以转换位B+C=A，这个题不允许有前导零，0这个数也是不行的，我们从个位开始同时对B,

布满荆棘的人生/ 2022年05月14日 01:38/ 0 赞/ 261 阅读

相关 hdu 4628 Pieces（状态压缩＋记忆化搜索）

Pieces Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Oth

╰半橙微兮°/ 2022年03月30日 12:43/ 0 赞/ 223 阅读

相关 WuKong 最短路&&记忆化搜索

Problem Description Liyuan wanted to rewrite the famous book “Journey to the West” (“Xi

古城微笑少年丶/ 2022年01月08日 01:53/ 0 赞/ 245 阅读