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

?

?

1 楼 笔良文昌 2012-02-29 怒搞DP。 Orz~ 2 楼 暴风雪 2012-02-29 笔良文昌 写道怒搞DP。 Orz~
吊得一逼……