题解：P11595 [NOISG2018 Finals] Journey

tjdyzh · 2025-01-23 16:13:13 · 题解

主要思路

对于本题，就我而言，第一眼并没有想到动态规划，随即，我打了 dfs。

朴素 dfs

定义函数 dfs(u,val) 表示现在在城市 u 且时间为 val，按题意模拟即可，20 分。

#include<bits/stdc++.h>
using namespace std;
const int inf=5e8+1;
struct node{
    int v,w;
    node(){
        v=w=0;
    }
    node(int x,int y){
        v=x;
        w=y;
    }
};
vector<node> e[10010];
//邻接表存图
int ans[410];
int n,m,h;
void dfs(int u,int val){
    //搜到目标，计入答案，跳出递归
    if(u==n-1){
        if(ans[val]==inf) return;
        ans[val]++;
        return ;
    }
    for(auto t:e[u]){
    //沿边搜索
        int v=t.v;
        int w=val+t.w;
        if(w>m){
            continue;
        }
        for(int i=w;i<=m;i++){
            dfs(v,i);
        }
    }
}
int main(){
  //关同步流
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>h;
    for(int i=0;i<n-1;i++){
        for(int j=1;j<=h;j++){
            int v,w;
            cin>>v>>w;
            e[i].push_back(node(v,w));
      //建边
        }
    }
    dfs(0,1);
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<' ';
    }
    return 0;
}

记忆化搜索

定义函数 dfs(u,val) 表示现在在城市 u 且时间为 val，令 f_{i,j} 表示现在在城市 i 且时间为 j 的方案数，由于递归的劣势，43 分。

#include<bits/stdc++.h>
using namespace std;
const int inf=5e8+1;
struct node{
    int v,w;
    node(){
        v=w=0;
    }
    node(int x,int y){
        v=x;
        w=y;
    }
};
vector<node> e[10010];
int n,m,h;
int f[10010][410];
int dfs(int u,int val){
    int sum=0;
    if(f[u][val]!=0){
        return f[u][val];
    }
    if(u==0&&val==1){
        return 1;
    }
    for(auto t:e[u]){
        int v=t.v;
        int w=val-t.w;
        for(int i=w;i>=1;i--){
            sum+=dfs(v,i);
        }
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>h;
    for(int i=0;i<n-1;i++){
        for(int j=1;j<=h;j++){
            int v,w;
            cin>>v>>w;
            if(v>i)
            e[v].push_back(node(i,w));
        }
    }
    for(int i=1;i<=m;i++){
        cout<<dfs(n-1,i)<<' ';
    }
    return 0;
}

动态规划

由记忆化搜索更改为递推形式，得出动态规划 AC 代码。

#include<bits/stdc++.h>
using namespace std;
const int inf=5e8+1;
struct node{
    int v,w;
    node(){
        v=w=0;
    }
    node(int x,int y){
        v=x;
        w=y;
    }
};
vector<node> e[10010];
int n,m,h;
int f[10010][410];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>h;
    f[0][1]=1;
    for(int i=0;i<n-1;i++){
        for(int j=1;j<=h;j++){
            int v,w;
            cin>>v>>w;
            if(v>i)
            e[i].push_back(node(v,w));
        }
    }
    for(int i=0;i<n-1;i++){
        if(i!=0)
            for(int j=1;j<=m;j++){
                f[i][j]+=f[i][j-1];
                if(f[i][j]>inf) f[i][j]=inf;
            }
        for(auto t:e[i]){
            int v=t.v;
            int w=t.w;
            for(int j=w;j<=m;j++){
                f[v][j]+=f[i][j-w];
                if(f[v][j]>inf) f[v][j]=inf;
            }
        }
    }
    for(int j=1;j<=m;j++){
        f[n-1][j]+=f[n-1][j-1];
        if(f[n-1][j]>inf) f[n-1][j]=inf;
    }
    for(int i=1;i<=m;i++){
        cout<<f[n-1][i]<<' ';
    }
    return 0;
}