大致题意:
给出一个正整数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;
}
分享到:
相关推荐
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
1. **学习算法与数据结构**:HDOJ包含了丰富的算法题目,如排序、搜索、图论、动态规划、贪心算法等,是学习和提升算法能力的理想平台。通过解决这些题目,你可以深入理解各种算法的实际应用和性能分析。 2. **提高...
【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
hdoj1001标程
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1008
ACM ICPC HDOJ1003
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
“hdoj 2013 多校训练2标程+解题报告”这个标题指的是2013年举行的一场由hdoj(HDU Online Judge,即杭州电子科技大学在线评测系统)组织的多校联合编程训练活动的第二阶段。其中,“标程”是指官方提供的正确解答...
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...
### hdoj杭电入门训练题 #### 概述 杭电在线评测系统(HDOJ)是中国杭州电子科技大学提供的一套在线编程题库平台,主要用于计算机程序设计竞赛(ACM-ICPC)的训练与选拔。对于初学者而言,通过解决HDOJ中的题目可以...