频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 3249 Test for Job(记忆化搜索)
2013-07-26 11:20:06           
收藏   我要投稿

题意:给定一个有向无环图,每个结点有权值,从入度为零的点作为起点,出度为零的点作为终点,要求出到终点时可能的最大权值(权值可能为负数,不过都不超过int)

思路:记忆化搜索,很多人反向建图来做,不知道有什么好处。我还是正常顺序。事先记录好各点的入度,枚举这些点搜索出的可能最大权值。

这种题目的状态转移方程还是很好分析的dp[i] = v[i] + max(dp[u0],dp[u1],......,dp[un]);  u0--un为i连接的结点。此外点过多,用邻接表存储。

 

 


 
#include <cstdio>   
#include <cstring>   
#include <iostream>   
#include <vector>   
#include <cmath>   
#define MAX 111111   
#define INF 0x7FFFFFFF   
using namespace std;  
  
vector<int> edge[MAX];  
int v[MAX],dp[MAX],deg[MAX];  
int n,m;  
  
void init() {  
    for(int i=0; i<=MAX; i++) {  
        dp[i] = -INF;  
        edge[i].clear();  
    }  
    memset(deg,0,sizeof(deg));  
}  
  
int dfs(int v0) {  
    if(dp[v0] != -INF) return dp[v0];  
    int size = edge[v0].size();  
    if(size == 0) return v[v0];  
    int maxx = -INF;  
    for(int i=0; i<size; i++) {  
        int u = edge[v0][i];  
        maxx = max(maxx,dfs(u));  
    }  
    return dp[v0] = v[v0] + maxx;  
}  
  
int main() {  
    int i,j,a,b;  
    while(scanf("%d%d",&n,&m) != EOF) {  
        init();  
        for(i=1; i<=n; i++) {  
            scanf("%d",&v[i]);  
        }  
        for(i=1; i<=m; i++) {  
            scanf("%d%d",&a,&b);  
            edge[a].push_back(b);  
            deg[b] ++;  
        }  
        int maxx = -INF;  
        for(i=1; i<=n; i++) {  
            if(!deg[i]) {  
                maxx = max(maxx,dfs(i));  
            }  
        }  
        printf("%d\n",maxx);  
    }  
    return 0;  
}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 记忆
上一篇:POJ搜索专题(转转)
下一篇:hdu 4300 Clairewd’s message(KMP)
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站