zoj 3626 Treasure Hunt I(树形DP+分组背包)-白红宇

zoj 3626 Treasure Hunt I(树形DP+分组背包)

阅读量：4035 次

发布时间：2019-05-24

本文共 834 字，大约阅读时间需要 2 分钟。

1、

2、题目大意：

有n个城镇，他们之间有路相通，知道每条路需要走的天数，每个城镇的价值，现在一个人想要从k点出发，在m天内去访问别的城镇，但是必须在m天之前返回k点，求可以获得的最大价值

dp[i][j]表示从i点出发走j天获得的最大价值，需要往返，注意m/=2即可

状态转移方程

dp[u][j]=max(dp[u][j],dp[u][j-k-w[u][v]]+dp[v][k]);

3、AC代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define N 105int val[N];vector
       
         adj[N*2];int w[N][N];int dp[N][N],vis[N],m;void dfs(int u){    vis[u]=1;    dp[u][0]=val[u];    for(int i=0;i
        
         =0;j--) { for(int k=0;k<=j-w[u][v];k++) { dp[u][j]=max(dp[u][j],dp[u][j-k-w[u][v]]+dp[v][k]); } } } }}int main(){ int n,a,b,c,k; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) adj[i].clear(); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&val[i]); dp[i][0]=val[i]; } for(int i=1;i
         
          ans) ans=dp[k][i]; } printf("%d\n",ans); } return 0;}