题目描述

https://www.luogu.com.cn/problem/P1460
洛谷得一道题。

样例

blablabla

C++ 代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int N=1010;



int a[N]={0},b[N][N]={0},v,g;
int temp[N]={0},res[N]={0};//res记录方案编号

int temp1[N]={0},mm=0;
int gg[N]={0};

bool camp(int p[])
{
    for(int i=0;i<v;i++)
    {
        if(a[i]>p[i]) return false;
    }

    return true ;
}

void dfs(int n)//n表示已经枚举得方案数
{
    //如果已经枚举了大于等于1个方案，则看一下是否有满足条件的
    if(n>=1&&camp(temp))
    {
        if(n<mm||mm==0)
        {
        mm=n;
        for(int i=0;i<mm;i++)
          res[i]=temp1[i];//最终只打印前mm个数,也即答案数目
        }

        return ;
    }

     for(int i=temp1[n-1];i<g;i++)//枚举每种方案得组合,由此可转化为类似全排列问题,i表示方案!!!所以一定要从temp1[n-1]开始！！！
     {
    if(gg[i]) continue ;
      if(!gg[i]){
      gg[i]=1;
      for(int j=0;j<v;j++)
        temp[j]+=b[i][j];//第i种方案得第j个饲料得维他命含量

           temp1[n]=i;//i为方案编号,将已经枚举得方案编号记录下来
           dfs(n+1);

      for(int t=0;t<v;t++)//回溯
        temp[t]-=b[i][t];
        gg[i]=0;
                }

     }

     return ;
}

int main()
{
    scanf("%d",&v);
    for(int i=0;i<v;i++) scanf("%d",&a[i]);

    scanf("%d",&g);//方案数
    for(int i=0;i<g;i++)
        for(int j=0;j<v;j++)
                scanf("%d",&b[i][j]);

    dfs(0);

    printf("%d ",mm);
    for(int i=0;i<mm;i++)
        printf("%d ",res[i]+1);
    return 0;
}