USACO备考冲刺必刷题 | P1460 Healthy Holsteins

2023年12月10日19:40:07 教育 1979

学习C++从娃娃抓起!记录下USACO(美国信息学奥赛)备考学习过程中的题目,记录每一个瞬间。

附上汇总贴:USACO备考冲刺必刷题 | P1460 Healthy Holsteins - 天天要闻

#include <bits/stdc++.h>
using namespace std;
int vType, fType, p;
int v[30], f[20][30], sel[20], ans[20];
int minSelCnt = 20;
bool check(int selCnt)  // 定义维他命检查函数
{
    for (int i=1; i<=vType; i++) {  // 依次遍历所有维他命种类
        int sum = 0;  // 定义每种维他命的总数,每次循环初始为0
        for (int j=1; j<=selCnt; j++) {  // 依次遍历选择的那些饲料
            sum += f[sel[j]][i];  // sum加上选择的饲料编号的维他命值
        }
        if (sum<v[i]) {  // 如果总和
            return false;
        }
    }
    return true;
}
void dfs(int pos, int cnt)  // 定义dfs函数,pos为饲料编号,cnt为饲料选择的数量
{
    if (pos > fType) {  // dfs退出条件,直到选到最后一种饲料编号
        if (check(cnt) && cnt < minSelCnt) {  // 如果此时选择的饲料的每种维他命之和大于最小维他命需要,且选择数量小于最小选择数量
            minSelCnt = cnt;  // 更新最小选择数量
            for (int i=1; i<=cnt; i++) {  // 更新结果数组,即更新为选择的饲料种类
                ans[i] = sel[i];  
            }
        }
        return;  // 一定要写!
    }
    sel[cnt+1] = pos;  // 选择编号为pos的饲料
    dfs(pos+1, cnt+1);  // 继续选择pos+1编号的饲料,cnt自增1
    sel[cnt+1] = 0;  // 不选编号为pos的饲料,不选就用0占位(这句可以忽略,因为下一句dfs中cnt不变,下次执行后会被修改)
    dfs(pos+1, cnt);  // 继续dfs搜索pos+1编号的饲料,但cnt不增加
}
int main()
{
    cin >> vType;  // 输入需要的维他命种类数
    for (int i=1; i<=vType; i++) {  // 遍历维他命种类数
        cin >> v[i];  // 输入每种维他命的最小量
    }
    cin >> fType;  // 输入饲料种数
    for (int i=1; i<=fType; i++) {  // for循环遍历饲料种数
        for (int j=1; j<=vType; j++) {  // for循环遍历维他命种类数
            cin >> f[i][j];  // 输入这种饲料各种维他命的值
        }
    }
    dfs(1, 0);  // 使用dfs搜索,起始饲料编号为1,0种选择
    cout << minSelCnt << " ";
    for (int i=1; i<=minSelCnt; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

【运行结果】

4
100 200 300 400
3
50  50  50  50
200 300 200 300
900 150 389 399
2 1 3 

教育分类资讯推荐

总报名人数19万 东莞市2025年初中学业水平考试今日开考 - 天天要闻

总报名人数19万 东莞市2025年初中学业水平考试今日开考

东莞市2025年初中学业水平考试(中考)6月30日-7月2日举行。2025年东莞全市初中学业水平考试总报名人数为19万人。其中初三中考8.8万名学生报名参加,设考点75个;初二生物地理学考有10.2万名学生报名参加,设考点80个。全市涉考工作人员超过2.4万人。上午7时38分,东莞市翰林实验学校小初部行政人员和老师齐聚综合楼一楼,...
北京大学2025“强基”真题!难度与创新并重,竞赛与高考衔接 - 天天要闻

北京大学2025“强基”真题!难度与创新并重,竞赛与高考衔接

6月29日,北京大学2025年“强基计划”校测如期举行。测试的时间是2025年6月29日下午14:30-17:30。据悉,2025年北京大学“强基计划”校测,仍然采用笔试、面试、体测三种形式,变化最大的是笔试环节。2025年报考北京大学“强基计划”Ⅰ组理科专业和医学组专业的考生,校测笔试科目为数学、物理、化学三个学科。而报考Ⅱ组文...
所有考生,填报志愿需要一味求新吗?新专业新在哪里? - 天天要闻

所有考生,填报志愿需要一味求新吗?新专业新在哪里?

央视网消息:对于高考考生来说,眼下正是高考填报志愿的重要阶段。2025年高校招生新增了29种普通本科专业,进一步强化专业设置对国家战略急需和高质量发展需求的快速响应。这些新专业新在哪里?对于考生来说,填报志愿需要一味求新吗?
叮!您有一份虹口区暑期影视思政课大礼包,请查收 - 天天要闻

叮!您有一份虹口区暑期影视思政课大礼包,请查收

【来源:上海市人民政府_今日上海_便民提示】为进一步深化虹口区“大思政课”红色光影育人活动,7月至8月暑假期间,虹口区将在中共四大纪念馆和左联会址纪念馆等持续开展影视思政课。现场将引导观众,通过影前思考、互动答题以及分享感悟等环节,构建影视
新府学高中部2025毕业季 | 春风化雨念师恩,云程发轫赴山海 - 天天要闻

新府学高中部2025毕业季 | 春风化雨念师恩,云程发轫赴山海

新府学高中部2025毕业季-2025-新府学高中部2025“春风化雨念师恩,云程发轫赴山海”主题毕业季,这一盛大活动由顺义区教育委员会主办,新府学承办,不仅彰显了学校对毕业生们的深切关怀,更体现了顺义区教育委员会对青少年成长教育的高度重视。
合肥市和平小学第二小学毕业典礼隆重举行 - 天天要闻

合肥市和平小学第二小学毕业典礼隆重举行

6月25日下午,合肥市和平小学第二小学隆重举办一场饱含深情的毕业典礼。校长吴维德、副书记李冉、副校长路遥、张红,六年级全体师生及学生家长共同见证了这一难忘时刻,这场充满仪式感的典礼,不仅为学子们镌刻下珍贵的童年印记,更是一堂生动的思政课,传