POJ 3249 Test for Job（DAG上的dp + 记忆化搜索）

╰半橙微兮° 2024-02-17 19:17 59阅读 0赞

题意：出发点（入度为0），终点（出度为0），都可能不止一个；求从出发点到目标点的最大收获或最少消费（有些城市值为负，表示消费）

思路：记忆化搜索避免超时。

AC代码如下：

#include<cstdio>
    #include<cstring>
    #include<vector> 
    #include<algorithm>
    using namespace std;
    #define INF 2147483647
    const int maxn=1e5+10;
    int v[maxn];   //保存值 
    int d[maxn];  //用于记忆化搜索 
    int root[maxn]; //统计入度 
    int n,m;
    vector<int>vec[maxn];
    int dp(int i){
    	int&ans=d[i];
    	if(ans!=0)return ans;
    	int len=vec[i].size();
    	if(len==0)return v[i];
    	ans=-INF;
    	for(int j=0;j<len;j++)
    	 ans=max(ans,dp(vec[i][j])+v[i]);
    	 return ans;
    }
    int main(){
    	while(scanf("%d%d",&n,&m)==2){
    		memset(d,0,sizeof(d));
    		memset(root,0,sizeof(root));
    		for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    		for(int i=1;i<=m;i++){
    		int a,b;
    		scanf("%d%d",&a,&b);
    		vec[a].push_back(b);
    		root[b]++;
    		}
    		int ans=-INF;
    		for(int i=1;i<=n;i++){
    			if(!root[i]) //刚开始没用这个判断，当所有点的值大于0时没问题，小于0就会出问题了 
    			ans=max(ans,dp(i));
    		}
    		printf("%d\n",ans);
    		for(int i=1;i<=n;i++)
    		vec[i].clear();
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 poj1661 Help Jimmy（记忆化搜索）

Help Jimmy <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

灰太狼/ 2024年02月18日 18:52/ 0 赞/ 64 阅读

相关 poj3249(记忆化搜索)Test for Job

Test for Job <table> <tbody> <tr> <td><strong>Time Limit:</strong> 5000MS

朱雀/ 2024年02月17日 23:35/ 0 赞/ 64 阅读

相关 POJ 3249 Test for Job（DAG上的dp + 记忆化搜索）

题意：出发点（入度为0），终点（出度为0），都可能不止一个；求从出发点到目标点的最大收获或最少消费（有些城市值为负，表示消费）思路：记忆化搜索避免超时。 AC代码如下：

╰半橙微兮°/ 2024年02月17日 19:17/ 0 赞/ 60 阅读

相关 POJ 1088 记忆化搜索经典

滑雪 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td> <td>&

红太狼/ 2024年01月22日 06:15/ 0 赞/ 101 阅读

相关 POJ 3249-Test for Job(拓扑排序&&DP)

Test for Job <table> <tbody> <tr> <td><strong>Time Limit:</strong> 5000MS</t

Love The Way You Lie/ 2022年08月21日 13:42/ 0 赞/ 23 阅读

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

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

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

相关 poj1088滑雪 (记忆化搜索)

Michael喜欢滑雪这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载

今天药忘吃喽~/ 2022年06月18日 11:28/ 0 赞/ 217 阅读

相关 B - 滑雪 POJ - 1088——dfs+记忆化搜索

Think: 1知识点：dfs+记忆化搜索 1>记忆化搜索=搜索的形式+动态规划的思想 2>记忆化搜索简介：记忆化搜索：算法上依然是搜索的流程，但是搜索到的一

阳光穿透心脏的1/2处/ 2022年06月11日 04:06/ 0 赞/ 216 阅读

相关 POJ 2738 Two Ends（记忆化搜索+dp）

In the two-player game "Two Ends", an even number of cards is laid out in a row. On each

落日映苍穹つ/ 2022年06月10日 05:18/ 0 赞/ 175 阅读

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

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

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