自动搬运

查看原文

来自洛谷，原作者为

	tjdyzh 因佳人初醒，辰星复天明。

搬运于2025-08-24 23:08:41，当前版本为作者最后更新于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;
}