USACO Section2.1 Healthy Holsteins 解题报告【icedream61】

　　　　holstein解题报告

------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　你需要给一头奶牛制定最优的喂养计划。
　　有V种维他命，每天对于每种维他命，牛都有需要达到的指标；
　　同时你有G种饲料，编号依次为1到G，每种维他命在每种饲料中所蕴含的量都会给你。
　　请你从中选出N种饲料，在达到指标的前提下让N最小。
【数据范围】
　　1<=V<=25
　　1<=每种维他命的指标<=1000
　　1<=G<=15
【输入格式】
　　第一行是V，后面V行依次给出1号到V号维他命的指标；
　　下面一行是G，后面G行依次是G种饲料，每行V个数，分别代表本饲料中各种维他命的含量。
【输出格式】
　　仅一行，各数用空格隔开。
　　第一个数是所需的饲料种数N，后面N个数依次是所选饲料的编号。
　　注意，若有多种方案N相同，则仅输出字典序最小的一组方案。
【输入样例】
　　4
　　100 200 300 400
　　3
　　50 50 50 50
　　200 300 200 300
　　900 150 389 399
【输出样例】
　　2 1 3
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　这题做法是枚举。
　　V种维他命，G份饲料，不妨考虑最大值G=15、V=25。每种饲料枚举取or不取，大约是300,000种情况；每种情况分别用来更新当前最优解，耗时大约不到400。如此可见，本题枚举时间大约在120,000,000，而枚举法常数很小，故而完全可以在1s内完成。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　第二次提交AC。第一次犯了点细节错误，把G和V有点弄混的地方。
【吐槽】
　　这题我严重被自己坑了。。
　　一开始根本没往枚举法上想，觉得USACO Section2.1的题，怎么也应该有道难题了。。结果想了好长时间没想出做法来，然后一看——这G只有15！这不是完全可以枚举吗……

【再次吐槽】

　　博文竟然有重名。。今后解题报告标题后面都加上我id，我就不行还有重名-.-

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

 /*

 ID: icedrea1

 PROB: holstein

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 int V,G;

 int v[+],g[+][+];

 bool now[+];

 int r,s[+];

 bool good[+];

 bool better()

 {

     for(int k=;k<=G;++k)

     {

         if(now[k] && !good[k]) return true;

         if(!now[k] && good[k]) return false;

     }

 }

 void Try()

 {

     int cnt=,sum[+]={};

     for(int k=;k<=G;++k)

         if(now[k])

         {

             ++cnt;

             for(int i=;i<=V;++i) sum[i]+=g[k][i];

         }

     for(int i=;i<=V;++i)

         if(sum[i]<v[i]) return; // 失败

     if(cnt<r || cnt==r && better())

     {

         r=cnt;

         for(int k=;k<=G;++k) good[k]=now[k];

     }

 }

 void go(int k) //前k组要不要已定

 {

     if(k==G) { Try(); return; }

     ++k; go(k);

     now[k]=true; go(k); now[k]=false;

 }

 int main()

 {

     ifstream in("holstein.in");

     ofstream out("holstein.out");

     in>>V;

     for(int i=;i<=V;++i) in>>v[i];

     in>>G;

     for(int k=;k<=G;++k)

         for(int i=;i<=V;++i) in>>g[k][i];

     r=G+; go();

     out<<r;

     for(int k=;k<=G;++k)

         if(good[k]) out<<" "<<k;

     out<<endl;

     in.close();

     out.close();

     return ;

 }

巴特西

USACO Section2.1 Healthy Holsteins 解题报告【icedream61】

最新文章

热门文章

巴特西

USACO Section2.1 Healthy Holsteins 解题报告 【icedream61】

最新文章

热门文章

USACO Section2.1 Healthy Holsteins 解题报告【icedream61】