关于搜索的分支
查看原帖
关于搜索的分支
250699
mot1ve楼主2020/9/2 19:51

为什么把dfs函数里的最后一个分支注释掉是对的?这样不会少一种情况吗?

//如果新开一张专辑,后面的曲子就不能放到前一张专辑里了 
#include<bits/stdc++.h>
using namespace std;
int n,t,m,ans;
int a[10010];
void dfs(int x,int now,int y,int sum)//x表示当前在考虑第几首曲子,now表示当前专辑已经用了的时间,y表示当前在考虑第几张专辑,sum表示已经装进去的曲子数目,
{
	if(x==n+1||y==m+1)
	{
		ans=max(ans,sum);
		return ;
	}
	if(a[x]<=t-now)
	{
		if(a[x]<t-now)//换不换都行,两个分支,如果恰好等于只能换。 
		dfs(x+1,now+a[x],y,sum+1);//录入+不换碟片
		dfs(x+1,0,y+1,sum+1);//如果是等于的话,只能是录入,换碟片。 
	}
	dfs(x+1,now,y,sum);//不录入,不换碟片
	//dfs(x+1,0,y+1,sum);//不录入,换碟片 
} 
int main()
{
	cin>>n>>t>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	dfs(1,0,1,0);
	cout<<ans;
	return 0;
}
2020/9/2 19:51
加载中...