[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~