<output id="qn6qe"></output>

    1. <output id="qn6qe"><tt id="qn6qe"></tt></output>
    2. <strike id="qn6qe"></strike>

      亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12
      書山有徑勤為路>>>>>>>>

      <<<<<<<<學海無涯苦作舟!

      加上減去DFS解決USACO Healthy Holsteins


      Description

      Farmer John prides himself on having the healthiest dairy cows in the world. He knows the vitamin content for one scoop of each feed type and the minimum daily vitamin requirement for the cows. Help Farmer John feed his cows so they stay healthy while minimizing the number of scoops that a cow is fed.

      Given the daily requirements of each kind of vitamin that a cow needs, identify the smallest combination of scoops of feed a cow can be fed in order to meet at least the minimum vitamin requirements.

      Vitamins are measured in integer units. Cows can be fed at most one scoop of any feed type. It is guaranteed that a solution exists for all contest input data.

      Input
      Line 1: integer V (1 <= V <= 25), the number of types of vitamins
      Line 2: V integers (1 <= each one <= 1000), the minimum requirement for each of the V vitamins that a cow requires each day
      Line 3: integer G (1 <= G <= 15), the number of types of feeds available
      Lines 4..G+3: V integers (0 <= each one <= 1000), the amount of each vitamin that one scoop of this feed contains. The first line of these G lines describes feed #1; the second line describes feed #2; and so on.
      Output

       

      The output is a single line of output that contains:

      • the minimum number of scoops a cow must eat, followed by:
      • a SORTED list (from smallest to largest) of the feed types the cow is given

      If more than one set of feedtypes yield a minimum of scoops, choose the set with the smallest feedtype numbers.

       

      Sample Input

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

      Sample Output

      2 1 3

      //加上減去深搜法

       

      #include <iostream>
      #include <string.h>
      using namespace std;
      
      
      int m,n,t;
      int v[30],vi[30][30]; //v記錄目標, vi記錄可用選擇
      int total,p[30],ni[30];
      bool line[30];

      bool check()
      {
      for (int i = 0; i < m; i++)
      if(p[i] < v[i]) return false; //只要有一個不滿足就不行
      return true;
      }

      void search(int k,int depth)
      {
      if(check() && depth < total) //遞歸的結束控制
         {
      total = depth;
      t = 0;
      for (int i = 0; i < n; i++)
      if(line[i]) ni[t++] = i+1; //記錄行號
      return;
      }
      for (int i = k+1;i < n; i++)
      {
      for (int j = 0; j < m; j++)
      p[j]+=vi[i][j]; //再增加一排進行搜索
      line[i] = true;
      search(i,depth+1); //對應的depth要加1.
      for (int j = 0; j < m; j++)
      p[j]-=vi[i][j]; //將p[j]復原
      line[i] = false;
      }
      }

      int main()
      {
      cin >> m;
      for (int i = 0; i < m; i++)
      cin >> v[i];
      cin >> n;
      for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
      cin >> vi[i][j];
      total = 100;
      memset(p,0,sizeof(p));
      memset(line,false,sizeof(line));
      for (int i = 0; i < n; i++) //i表示第i+1排
      {
      for (int j = 0; j < m; j++) //j表示第j+1列
      p[j]+=vi[i][j]; //p[j]表示有i+1排時,第j列的和。
      line[i] = true; //將第i排標記為正在使用中
      search(i,1);
      for (int j = 0; j < m; j++)
      p[j]-=vi[i][j]; //將p[j]復原
      line[i] = false;
      }
      cout << total <<" ";
      t = 0;
      for (int i = 0; i < total-1; i++)
         cout << ni[i] <<" ";
      cout << ni[total-1] << endl;
      return 0;
      }



      posted on 2011-10-23 14:47  More study needed.  閱讀(428)  評論(0)    收藏  舉報

      導航

      書山有徑勤為路>>>>>>>>

      <<<<<<<<學海無涯苦作舟!

      主站蜘蛛池模板: 国产边打电话边被躁视频| 常熟市| 午夜一区二区三区视频| 国产一区二区三区精品综合| 亚洲欧洲久久激情久av| 亚洲色婷婷一区二区| 成人aⅴ综合视频国产| 色婷婷日日躁夜夜躁| 少妇的丰满3中文字幕| 无码视频一区二区三区| 亚洲精品日韩中文字幕| 博爱县| 日韩av无码一区二区三区| 亚洲人成电影网站 久久影视 | 少妇久久久被弄到高潮| 亚洲码与欧洲码区别入口| 日韩少妇人妻vs中文字幕| 波多野结衣一区二区三区高清av| 亚洲电影天堂av2017| 国产乱码精品一区二区三区四川人| 久久精品久久电影免费理论片| 人妻体内射精一区二区三区| 五月天国产成人av免费观看| 久久亚洲精品人成综合网| 99精品国产精品一区二区| 中文在线最新版天堂| 亚洲www永久成人网站| 华人在线亚洲欧美精品| 伊吾县| 1精品啪国产在线观看免费牛牛| 欧美黑人性暴力猛交在线视频 | 国产欧美日韩高清在线不卡| 人妻激情视频一区二区三区| 国产午夜福利短视频| 伊人av超碰伊人久久久| 91高清免费国产自产拍| 免费观看全黄做爰大片| 亚洲中文字幕乱码一区| 欧美成人午夜在线观看视频| 欧美色aⅴ欧美综合色| 亚洲永久精品日韩成人av|