洛谷 U6931 灯光
题目背景
明天就是校园活动了，小明作为场地的负责人，将一切都布置好了。但是在活动的前几天，校园里的灯却都坏掉了，无奈之下，只好再去买一批灯。但是很遗憾的是，厂家看马上要过年了，就没有在进货了，现在只剩下n个发光值不同的灯，作为负责人，你需要，想办法配出合适的灯。
题目描述
厂家有n盏剩下的灯，小明需要m盏灯，因为活动举办在晚上，所以这些灯的光值和不能低于k，现在小明想知道，有多少种选灯的方案，以及每种方案选出的m盏灯。
输入输出格式
输入格式：
共n+1行，第一行有三个整数：n，m，k，表示厂家有n盏（灯），小明需要m盏，从n盏中选的m盏的光线和不能小于k。
接下来的1行，共n个整数，第i个数表示第i盏灯的发光值。
输出格式：
先输出一个整数，表示方案数，接下来的几行，每行m+1个数，前m个数表示每个方案选择的灯的序号，第m+1个数表示这个方案的光值和。
如果没有方案，第一行就输出-1，第二行输出最大的光亮值。
输入输出样例
输入样例#1：
3 2 5
1 3 2
输出样例#1：
1
2 3 5
输入样例#2：
4 2 7
2 5 3 1
输出样例#2：
2
1 2 7
2 3 8
输入样例#3：
5 2 5
2 2 2 2 2
输出样例#3：
-1
4
说明
- 数据说明
3<=m<=n<=20；
1<=k<=a[1]+a[2]...+a[n]；
样例就自己看哈~。
输出用序号排序
题目大意：有n个灯，选m个，要求选的m个灯的光值和大于k，求方案数及每个方案。
题解：搜索...
刚开始提交30分...思考人生.....
后来发现没有输出方案数...改了就A了...蠢哭....
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; int n,m,k,flag,max_ans,bo[22],ans[22]; vector<int>res[2000]; void dfs(int now,int has,int sum){ if(has==m){ if(sum>=k){ flag++; for(int i=1;i<=m;i++) res[flag].push_back(ans[i]); res[flag].push_back(sum); }else{ max_ans=max(max_ans,sum); } return; } if(now==n+1)return; ans[has+1]=now; dfs(now+1,has+1,sum+bo[now]); ans[has+1]=0; dfs(now+1,has,sum); } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++)scanf("%d",&bo[i]); dfs(1,0,0); if(!flag){ printf("-1 "); printf("%d ",max_ans); }else{ printf("%d ",flag); for(int i=1;i<=flag;i++){ for(int j=0;j<res[i].size();j++) printf("%d ",res[i][j]); printf(" "); } } return 0; }