为什么把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;
}