AcWing 1362. 健康的荷斯坦奶牛
原题链接
简单
作者:
ch_8
,
2021-01-07 17:44:35
,
所有人可见
,
阅读 433
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 15, M = 25;
int m,n;
int need[M],s[N][M],tmp[M];//tmp数组用来记录某一方案的维生素总和
bool st[N],res1[N]; // res1数组用来备份st数组
int res = 1e9;
bool check(){ //判断是否满足牛的需求
for(int i = 0;i < m;i ++)
if(tmp[i] < need[i])
return false;
return true;
}
void dfs(int u){
if(check()){ //满足需求并更新答案 同时return
int cnt = 0;
for(int i = 0;i < n;i ++) //统计用了多少行饲料
if(st[i]) cnt ++;
if(cnt < res){ //更新答案
res = cnt;
memcpy(res1,st,sizeof st); //res1数组用来备份当前最优解所选取的牛饲料行号
}
return ;
}
if(u == n){
return ; //遍历到最后一行也不满足 return
}
//下面是深搜的主要内容
//因为要保证字典序最小 所以尽量先选取行数较小的行
//即先"选取"->"dfs"->"回溯"->"dfs"
for(int i = 0;i < m;i ++){
tmp[i] += s[u][i];
}
st[u] = true;
dfs(u + 1); //这里的dfs是选取了某一行 之后开始下一行
for(int i = 0;i < m;i ++){ //回溯
tmp[i] -= s[u][i];
}
st[u] = false; //回溯
dfs(u + 1); //这里的dfs是未选取了某一行 之后开始下一行
}
int main(){
cin >> m;
for(int i = 0;i < m;i ++)
cin >> need[i];
cin >> n;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
cin >> s[i][j];
dfs(0);
cout << res << " ";
for(int i = 0;i < n;i ++)
if(res1[i])
cout << i + 1 << " "; //输出要求下标从1开始 所以要加1
return 0;
}