[DP+记忆化搜寻]hdoj 1224：Free DIY Tour

[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;
}