usaco_Healthy Holsteins_dfs

发布于 2019-05-10  6 次阅读


题目描述

农民JOHN以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛,以保持它们的健康,使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命量,输出喂给牛需要哪些种类的饲料,且所需的饲料剂量最少。

维他命量以整数表示,每种饲料最多只能对牛使用一次,数据保证存在解。


思路

暴力搜索每一个点,选或不选,如果当前个数比最小个数要小就搜下去,不然就退出
O(2^m)


/*
ID: a1192631
PROG: holstein
LANG: C++
*/
#include 
int a[26][26];
int f[26],fl[26],ll[26];
int n,m,ans=0,min=1000;
int dfs(int dep)
{
    if (dep>m) return 0;
    int t=0;
    for (int i=1;i<=n;i++)
    {
        f[i]-=a[dep][i];
        if (f[i]<=0) t++;
    }
    fl[dep]=1; ans++;
    if (t==n)
    {
        for (int i=1;i<=m;i++)
            ll[i]=fl[i];
        min=ans;
    }
    if (ans+1
]]>