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月7日至8日,湖北省蘄春縣多部門聯動,攜手織就全方位護航網,為考生和家長提供貼心服務,全力保障高考平穩有序進行。在蘄春一中、縣實驗高中、縣實驗中學、縣實驗小學4個考點,縣城管執法局貼心設立高考便民服務點。現場不僅為考生免費提供飲用水,還備足麵包、雨傘等愛心物資,為考生應對...
如果重回高考,是否還會選擇電氣專業? - 天天要聞

如果重回高考,是否還會選擇電氣專業?

又是一年高考季,萬千學子站在人生的十字路口,即將面對擇校與選專業的難題。作為電網行業的一名「過來人」,大家不禁思考:如果時光倒流,我還會選擇當時的專業嗎?專業的抉擇電氣哥找到了2024百度十大熱搜專業,我們一起來看一看。
N種守護,滿分安心,通山公安解鎖高考護航「方程式」 - 天天要聞

N種守護,滿分安心,通山公安解鎖高考護航「方程式」

當高考的鐘聲敲響,考場內是奮筆疾書的夢想追逐,考場外則是警民同心的溫暖守護。2025年高考期間,通山公安全體執勤民輔警用一場場「愛心接力」,為考生和家長排憂解難,書寫著一個個感人至深的故事。 01 緊急護送!爭分奪秒助考生 奔赴「正確戰場」 6月7日高考首日清晨,通山一中考點外,家長們踮腳張望,為孩子加油鼓勁。...
濟南市12355青少年服務台愛心助考服務溫暖護航 - 天天要聞

濟南市12355青少年服務台愛心助考服務溫暖護航

6月7日,2025年高考正式開啟,學子們數載耕耘積澱迎來綻放。在團市委的支持指導下,濟南市12355青少年服務台聯合區縣12355線下服務站,在歷下區、市中區、槐蔭區、天橋區、歷城區、平陰縣的7個高考考點外設置12355愛心助考服務點,全力
高考突發!考生撕毀試卷引熱議,備用卷真相曝光,網友:這操作太好了! - 天天要聞

高考突發!考生撕毀試卷引熱議,備用卷真相曝光,網友:這操作太好了!

據爆料視頻報道,6月7日上午,山東某高考考場內,監控畫面記錄下令人揪心的一幕:一名男生在考試過程中突然撕毀自己的試卷,隨後竟起身將魔爪伸向其他考生的試卷。視頻顯示,該考生先撕毀自己的答題卡,而後撕掉後面考試試卷,試圖撕毀右側及後側兩名考生的試卷。考場監考老師立即聯繫巡考人員將其帶離考場,整個過程未造成...
揭陽文明力量暖心守護5.2萬餘名趕考學子 - 天天要聞

揭陽文明力量暖心守護5.2萬餘名趕考學子

高考首日,晨曦微露,揭陽市的街頭巷尾早已涌動著一股溫暖的力量。今年高考季,揭陽有5.2萬餘名學子懷揣夢想,踏上高考的征程,走上逐夢的起點;而在他們的背後,一張張溫暖有力的「護航網」同步鋪開,覆蓋考點內外,延伸至城市的各個角落。