比赛 20140714上午练习 评测结果 AAAAAAAAAA
题目名称 荷斯坦奶牛 最终得分 100
用户昵称 noier 运行时间 0.012 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2014-07-14 10:33:53
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
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);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",&d[i][j]);
    ans=0xFFFFFFF;
    memset(bo1,false,sizeof(bo1));
    dfs(1);
    printf("%d",ans);
    for (int i=1;i<=m;i++)
        if (bo2[i]) printf(" %d",i);
    printf("\n");
    return 0;
}