本文主要是介绍HDU4571 记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2013 ACM-ICPC长沙赛区全国邀请赛
n个城市，m条路，总时间t，起始城市s，终点城市e
接下来给出各个城市的浏览时间，各个城市浏览后的满意程度。然后是m条路的信息。要求一个浏览顺序，使得总的满意程度最大，然后经过一个城市可以选择不去浏览，当前浏览城市的满意度一定要比前一个浏览城市的满意度高，并且最终要回到城市e。
floyd+记忆化搜索
#include "stdio.h"
#include "string.h"
#include "math.h"int inf=1000000000;
int cost[101],value[101];
int dis[101][101];
int dp[101][101][301];
int s,e,n;int Max(int a,int b)
{if (a<b) return b; else return a;
}
int dfs(int s,int v,int t)
{int i,ans;if (dis[s][e]>t) return -inf;if (dp[s][v][t]!=-1) return dp[s][v][t];ans=0;for (i=0;i<n;i++){if (dis[s][i]+cost[i]>t) continue;if (value[i]<=v) continue;ans=Max(ans,dfs(i,value[i],t-dis[s][i]-cost[i])+value[i]);}dp[s][v][t]=ans;return ans;
}void floyd()
{int i,j,l;for (i=0;i<n;i++)for (j=0;j<n;j++)for (l=0;l<n;l++)if (dis[j][i]+dis[i][l]<dis[j][l])dis[j][l]=dis[j][i]+dis[i][l];}int main()
{int Case,ii,m,t,i,j,a,b,c;scanf("%d",&Case);for (ii=1;ii<=Case;ii++){scanf("%d%d%d%d%d",&n,&m,&t,&s,&e);for (i=0;i<n;i++)scanf("%d",&cost[i]);for (i=0;i<n;i++)scanf("%d",&value[i]);for (i=0;i<n;i++)for (j=0;j<n;j++)if (i==j) dis[i][j]=0;elsedis[i][j]=inf;for (i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);if (c<dis[a][b])dis[a][b]=dis[b][a]=c;}floyd();memset(dp,-1,sizeof(dp));printf("Case #%d:\n",ii);printf("%d\n",dfs(s,0,t));}return 0;
}
这篇关于HDU4571 记忆化搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
