洛谷 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：

输入样例#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[],ans[];

vector<int>res[];

void dfs(int now,int has,int sum){

    if(has==m){

        if(sum>=k){

          flag++;

          for(int i=;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+)return;

    ans[has+]=now;

    dfs(now+,has+,sum+bo[now]);

    ans[has+]=;

    dfs(now+,has,sum);

}

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=n;i++)scanf("%d",&bo[i]);

    dfs(,,);

    if(!flag){

        printf("-1\n");

        printf("%d\n",max_ans);

    }else{

        printf("%d\n",flag);

        for(int i=;i<=flag;i++){

            for(int j=;j<res[i].size();j++)

            printf("%d ",res[i][j]);

            printf("\n");

        }

    }

    return ;

}

巴特西

洛谷 U6931 灯光

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章