比赛 20160708BDFS 评测结果 C
题目名称 荷斯坦奶牛 最终得分 0
用户昵称 不会起名怪我咯 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2016-07-08 10:03:36
显示代码纯文本
#include<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
bool bo1[26],bo2[26];
int a[26],s[26],d[26][26];
int n,m,ans;
void Count()
{
    int k=0;
    for (int i=1;i<=m;i++)
        if (bo1[i]) k++;
    if (k>=ans)
		return ;
    memset(s,0,sizeof(s));
    for (int i=1;i<=m;i++)
        if (bo1[i])
            for (int j=1;j<=n;j++)
                s[j]+=d[i][j];
    for (int i=1;i<=n;i++)
        if (a[i]>s[i]) 
			return ;
    ans=k;
    for (int i=0;i<=15;i++) 
		bo2[i]=bo1[i];
}
void dfs(int dep)
{
    if (dep==m+1)
    {
        Count();
		return ;
    }
    bo1[dep]=true;
    dfs(dep+1);
    bo1[dep]=false;
    dfs(dep+1);
}
int main()
{
    freopen("holstein.in","r",stdin);
    freopen("holstein.out","w",stdout);
    cin>>n;
    for (int i=1;i<=n;i++) 
		cin>>a[i];
    cin>>m;
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            cin>>d[i][j];
    ans=0xFFFFFFF;
    memset(bo1,false,sizeof(bo1));
    dfs(1);
    cout<<ans<<' ';
    for (int i=1;i<=m;i++)
        if (bo2[i])
			cout<<i<<' ';
    printf("\n");
    return 0;
}