题意: 一颗树有n个结点,每个结点有若干宝物,每条路径需要若干时间.一个人开始在结点1,问能不能在规定

的时间T内到达结点n. 若能, 算出他能在规定时间T内最多拿到多少宝物.

分析: 先DFS搜出结点1到结点n的路径及必过的结点并求出最短时间t,如果t超出T,则无法到达.

否则, 将必过的路径摧毁,记下能拿到的宝物数并且总时间减去t, 将必过的结点均作为0的子结点,路径为0.

这样则将树转换成以0为根结点. 此时只需求从0点开始在剩余时间(T-t)内最多能拿到多少宝物,普通DP即可.

代码:

 
#include   
#include   
#include   
#include   
  
using namespace std;  
const int maxn=105;  
  
vectorTree[maxn];  
int g[maxn][maxn],val[maxn];  
int dp[maxn][maxn*5];   
bool vis[maxn],vit[maxn][maxn],ok;  
int n,p,m,T,ans;  
void Init(){  
    for(int i=0;i<=n;++i) Tree[i].clear();  
    memset(g,0,sizeof(g));  
    memset(vis,false,sizeof(vis));  
    memset(vit,true,sizeof(vit));  
    ok=true; ans=0;  
}  
//搜索从n->1这条路径, 并将路径摧毁, 将必过的结点加到0的子结点, 把宝物值置0   
bool DFS(int cnt,int t){       
    vis[cnt]=true;  
    if(cnt==1){  
        Tree[0].push_back(cnt);                   // 作为0的子结点   
        ans+=val[cnt]; val[cnt]=0;                // 取走宝物, 并置0   
        if(t>=T) ok=false;  
        T-=t;                                     // 空余时间   
        return true;  
    }  
    int len=Tree[cnt].size();  
    for(int i=0;i=d;--j)  
            for(int k=j-d;k>=0;--k)  
                dp[cnt][j]=max(dp[cnt][j],dp[cnt][j-d-k]+dp[son][k]);  
    }  
}  
int main(){  
    while(~scanf("%d%d",&n,&T)){  
        Init();  
        for(int i=1;i
#include
#include
#include

using namespace std;
const int maxn=105;

vectorTree[maxn];
int g[maxn][maxn],val[maxn];
int dp[maxn][maxn*5]; 
bool vis[maxn],vit[maxn][maxn],ok;
int n,p,m,T,ans;
void Init(){
    for(int i=0;i<=n;++i) Tree[i].clear();
    memset(g,0,sizeof(g));
    memset(vis,false,sizeof(vis));
    memset(vit,true,sizeof(vit));
    ok=true; ans=0;
}
//搜索从n->1这条路径, 并将路径摧毁, 将必过的结点加到0的子结点, 把宝物值置0
bool DFS(int cnt,int t){     
    vis[cnt]=true;
    if(cnt==1){
        Tree[0].push_back(cnt);                   // 作为0的子结点
        ans+=val[cnt]; val[cnt]=0;                // 取走宝物, 并置0
        if(t>=T) ok=false;
        T-=t;                                     // 空余时间
        return true;
    }
    int len=Tree[cnt].size();
    for(int i=0;i=d;--j)
            for(int k=j-d;k>=0;--k)
                dp[cnt][j]=max(dp[cnt][j],dp[cnt][j-d-k]+dp[son][k]);
    }
}
int main(){
    while(~scanf("%d%d",&n,&T)){
        Init();
        for(int i=1;i