NOIP C++ 健康的荷斯坦 搜索问题

Question

题目链接：[](【腾讯文档】20210815-
腾讯文档 腾讯文档-在线文档 https://docs.qq.com/doc/DY1ZTTUl6RExaZHFV )

【题目描述】
农民约翰以拥有世界上最健康的奶牛为傲. 他知道每种饲料中所包含的牛所需的最低的维他命量是多少. 请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少.
给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少.
维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解.
输入格式
第1行：一个整数V(1\le V\le 25)V(1≤V≤25),表示需要的维他命的种类数.
第2行：VV个整数(1\le(1≤每个数\le 1000)≤1000),表示牛每天需要的每种维他命的最小量.
第3行：一个整数G(1\le G\le 15)G(1≤G≤15),表示可用来喂牛的饲料的种数.
下面GG行，第n行表示编号为n饲料包含的各种维他命的量的多少.
输出格式
输出只有一行，包括
牛必需的最小的饲料种数PP
后面有PP个数，表示所选择的饲料编号（按从小到大排列）.
如果有多个解，输出饲料序号最小的（即字典序最小）.
输入样例#1
4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399

输出样例#1
输出#1
2 1 3

Answer 1

DFS?

#include<bits/stdc++.h>
#define LL long long
#define maxn (int)1e5
#define INF 0x3f3f3f3f
using namespace std;
int ans[50];
int arr[50][1200];
int pre[50];
int step;
 int T; int n,m;
 string S[maxn];
 char c[maxn];
 int sum[1200];
 int I=1;
 bool cmp(string a,string b)//排序，先按种类编号的个数排列，再按字典序排
 {
     if(a.size()!=b.size())  return a.size()<b.size();
     else return a<b;
 }
void dfs(int idx)
{
    if(idx>n){//判断
            memset(sum,0,sizeof(sum));
        for(int i=1;i<=step;++i)
        {
            int k=pre[i];
            for(int j=1;j<=T;++j)
              sum[j]+=arr[k][j];
        }
        bool r=1;
        for(int i=1;i<=T;++i)
        if(ans[i]>sum[i]) {
            r=0;break;
        }
        if(r==1) {//如果满足要求就保存到字符数组里
            for(int i=1;i<=step;++i)
            c[i]=pre[i]+'0';
            string ss(c+1,c+step+1);
            S[I++]=ss;
        }
        return ;
    }
    pre[++step]=idx;
    dfs(idx+1);
    step--;
    dfs(idx+1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
 
    for(int i=1;i<=T;++i)
    {
        cin>>ans[i];
    }
    cin>>n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=T;++j)
         cin>>arr[i][j];
    step=0;
    dfs(1);
    sort(S+1,S+I,cmp);
   // for(int i=1;i<I;++i) cout<<S[i]<<" ";
    cout<<S[1].size();
    int k=0;m=0;
    for(int i=0;i<S[1].size();++i)
    {
        k=k*10+(S[1][i]-'0');//因为是字符串，4，14写成414，但是编号最多十几，且编号按从小到大排列
        if(m<k) {
                cout<<" "<<k;
            m=k;k=0;
        }
 
    }
 
}