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 

教育分類資訊推薦

全國多地高考今日結束,考後要警惕這件事 - 天天要聞

全國多地高考今日結束,考後要警惕這件事

中新網北京6月9日電(李京統)6月9日,2025年全國高考進入第三天,多數省份的高考將迎來收官。如河北、山西、吉林、江蘇等多地將於今日結束全部考試,而北京、天津、浙江、山東等地的考試則將於明日結束。 接下來,考生將進入高考成績查詢及志願填報階段,多地已公布相關時間。6月7日,山西大同,考生在大同一中考點排隊進入...
“高考英語”衝上熱搜!熟悉的他又出現了 - 天天要聞

“高考英語”衝上熱搜!熟悉的他又出現了

2025年高考的英語科目考試已經結束,“高考英語”“新一卷英語難不難”等詞條衝上熱搜。 據了解 今年的英語作文里 一個熟悉的身影又出現了 ——沒錯,就是李華! 北京高考英語作文又見“李華”。6月8日16時30分,2025年北京高考英語科目考試結束。今年作文題目依然將考生身份設定為高三學生李華,請李華為外國好友要參加的...
初二這一年,你以為是升級,實際是分流 - 天天要聞

初二這一年,你以為是升級,實際是分流

小時候,我以為世界是按部就班的。你背會乘法口訣表,老師就會獎勵一張笑臉貼紙;你抄寫完生字,家長就會收下作業本點頭稱讚;考試認真點,就能從班裡第十三名變成第十名,再湊合衝進前五,基本算天賦型選手。小學是個“打卡遊戲”,過關斬將的快感里,藏着一
湖北蘄春縣多部門聯動,為考生和家長提供貼心服務 - 天天要聞

湖北蘄春縣多部門聯動,為考生和家長提供貼心服務

極目新聞記者 董淑健通訊員 陳祥6月7日至8日,湖北省蘄春縣多部門聯動,攜手織就全方位護航網,為考生和家長提供貼心服務,全力保障高考平穩有序進行。在蘄春一中、縣實驗高中、縣實驗中學、縣實驗小學4個考點,縣城管執法局貼心設立高考便民服務點。現場不僅為考生免費提供飲用水,還備足麵包、雨傘等愛心物資,為考生應對...