`
暴风雪
  • 浏览: 390682 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[DP+记忆化搜索]hdoj 1224:Free DIY Tour

阅读更多

大致题意:

    给出一个正整数n,并给出一个由n+1个点组成的DAG,每个点有一个权值,代表走到这个点后能得到的收益值,1和n+1点的收益值是0。求出从1点走到n+1点收益值最大是多少。

 

大致思路:
    DP,用记忆化搜索来实现。

 

 

#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=30015;
const int mMax=200005;
class edge{
public:
    int u,v,nex;
};edge e[mMax];
int k,head[nMax];

void addedge(int a,int b){
    e[k].u=a;
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}

long long  num[nMax];
long long dp[nMax],ans;
int n,res[nMax],cnt;

int dfs(int loc,int sum,int dep){
    int i,v,flag=0;
    if(dp[loc]>sum+num[loc])return 0;
    else dp[loc]=sum+num[loc];
    if(loc==n){
        ans=sum;
        cnt=dep;
        return 1;
    }
    for(i=head[loc];i;i=e[i].nex){
        v=e[i].v;
        if(dfs(v,dp[loc],dep+1)){
            res[dep]=loc;
            flag=1;
        }
    }
    if(flag) return 1;
    else return 0;
}

int main(){
    int cas,i,m,a,b,csn=0;
    scanf("%d",&cas);
    while(cas--){
        ans=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%lld",&num[i]);
        }
        num[++n]=0;
        k=1;
        memset(dp,0,sizeof(dp));
        memset(head,0,sizeof(head));
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&a,&b);
            addedge(a,b);
        }
        res[0]=1;
        dfs(1,0,1);   //位置,收获值,深度
        printf("CASE %d#\n",++csn);
        printf("points : %lld\n",ans);
        printf("circuit : ");
        for(i=1;i<cnt;i++){
            printf("%d->",res[i]);//cout<<res[i]<<"->";
        }cout<<1<<endl;
        if(cas!=0)cout<<endl;
    }
    return 0;
}
 

 

0
0
分享到:
评论
2 楼 暴风雪 2012-02-29  
笔良文昌 写道
怒搞DP。 Orz~

吊得一逼……
1 楼 笔良文昌 2012-02-29  
怒搞DP。 Orz~

相关推荐

    HDOJ DP题目总结

    一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧

    HDOJ题目分类 HDOJ题目分类

    【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...

    hdoj 2013 多校训练4标程+解题报告

    【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    HDOJ离线版

    1. **学习算法与数据结构**:HDOJ包含了丰富的算法题目,如排序、搜索、图论、动态规划、贪心算法等,是学习和提升算法能力的理想平台。通过解决这些题目,你可以深入理解各种算法的实际应用和性能分析。 2. **提高...

    HDOJ 80题 Java

    【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    HDOJ1002

    ACM ICPC HDOJ1002

    HDOJ1001

    ACM ICPC HDOJ1001

    hdoj1001标程

    hdoj1001标程

    hdoj1004 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    HDOJ 1008

    ACM ICPC HDOJ1008

    HDOJ1003

    ACM ICPC HDOJ1003

    ACM HDOJ 课件

    【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

    hdoj 2013 多校训练2标程+解题报告

    “hdoj 2013 多校训练2标程+解题报告”这个标题指的是2013年举行的一场由hdoj(HDU Online Judge,即杭州电子科技大学在线评测系统)组织的多校联合编程训练活动的第二阶段。其中,“标程”是指官方提供的正确解答...

    hdoj1002——大整数相加

    ### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...

    hdoj杭电入门训练题

    ### hdoj杭电入门训练题 #### 概述 杭电在线评测系统(HDOJ)是中国杭州电子科技大学提供的一套在线编程题库平台,主要用于计算机程序设计竞赛(ACM-ICPC)的训练与选拔。对于初学者而言,通过解决HDOJ中的题目可以...

    HDOJ.rar_HD_HDOJ

    【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...

Global site tag (gtag.js) - Google Analytics