10055: 超操的盖饭店2
题目描述
小a也开了一家盖饭店，超操的弟弟超操弟是厨师；
他会做n种盖饭，每种盖饭xi元
一天结束后，小a统计了账单得知今天卖了m元
输入
n,m
n行，表示n种盖饭的价格
输出
第1~ans行：各种盖饭卖了多少的每一种可能。
第ans+1行：可能的数量ans
样例输入 复制
3 26
10 15 1样例输出 复制
0 0 26
0 1 11
1 0 16
1 1 1
2 0 6
5提示
版权所有；未经允许，禁止抄袭翻用；
dfs全排列模板
#include<bits/stdc++.h> using namespace std;
int n;
int a[1000],vis[1000]; //a是存全排列的 vis存是否出现过
void dfs(int d){ //d代表第几个数字
if(d>n){ //假设n是4 d为5代表第5个数字，这时前4个已经设置到了
for(int i=1;i<=n;i++) //相应的应用
printf("%d ",a[i]);
cout<<endl;
return; //别忘了return
}
for(int i=1;i<=n;i++){ //设置当前第d个数字，可能是1~n的某一个
if(!vis[i]){ //i这个数字没有在a数组中、没有被选过
a[d] = i; vis[i] = 1;//第d个数字是i，且标记i被选了
dfs(d+1); //选下一个数字
vis[i] = 0; //“归”时将重新设置第d个数字进行尝试
} //所以之前设置的i取消标记
}
}
int main(){
cin>>n;//n个数字
dfs(1);//从第1个数字开始设置
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////记的删批注
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////