USACO chapter 2 section 2.1 Health Holsteins

USER: tianbing tianbing [tbbd4261]
TASK: holstein
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 2932 KB]
   Test 2: TEST OK [0.000 secs, 2932 KB]
   Test 3: TEST OK [0.022 secs, 2932 KB]
   Test 4: TEST OK [0.022 secs, 2932 KB]
   Test 5: TEST OK [0.011 secs, 2932 KB]
   Test 6: TEST OK [0.000 secs, 2932 KB]
   Test 7: TEST OK [0.000 secs, 2932 KB]
   Test 8: TEST OK [0.022 secs, 2932 KB]
   Test 9: TEST OK [0.032 secs, 2932 KB]
   Test 10: TEST OK [0.022 secs, 2932 KB]

All tests OK.

Your program ('holstein') produced all correct answers!  This is your
submission #4 for this problem.  Congratulations!

一定要审题,刚开始把题目看错了。
直接搜索所有情况,用cnt和ans[]分别纪录最小的种数及与最小种数对应的状态
DFS可以保证cnt相等时先搜到的比后搜到的字典序靠前

/*
ID:tbbd4261
PROG:holstein
LANG:C++
*/

#include<iostream>
#include<fstream>
#include<climits>
#include<cstring>
using namespace std;

ifstream fin("holstein.in");
ofstream fout("holstein.out");

int need[26]={0},
    amount[16][26]={0};
bool f[16]={0},ans[16]={0};
int now[26]={0};
int n,i,g,j,mmin=INT_MAX,cnt=INT_MAX;

int check()
{
   int sum=0;
   memset(now,0,sizeof now);
   for(int i=1; i<=g; i++)
   {        if(f[i])
            for(int j=1; j<=n; j++)
              now[j]+=amount[i][j];
   }
   bool flag=1; 
   for(int i=1; i<=n&&flag; i++)
   {
       sum+=now[i];
      if(now[i]<need[i]){ flag=0; break; }
   }
   if(flag)return sum;   //sum是多余的,原来以为要求和的 直接return falg;
   return 0;
}


void dfs(int deep,int count)
{
     if(deep>g)return ;
     int s;
     f[deep]=1;
     s=check();
     if(s>0&&count+1<cnt)
     {
           cnt=count+1;
           for(i=1; i<=g; i++)
              ans[i]=f[i];
     }
     dfs(deep+1,count+1);
     f[deep]=0;
     dfs(deep+1,count);
}

void input()
{
    fin>>n;  
    for(i=1; i<=n; i++)
       fin>>need[i];
    fin>>g;
    for(i=1; i<=g; i++)
    for(j=1; j<=n; j++)
      fin>>amount[i][j];
}

void solve()
{
    dfs(1,0);
    fout<<cnt;
    for(int i=1; i<=g; i++)
         if(ans[i])fout<<' '<<i;
    fout<<endl;
}
    
int main()
{
    input();
    solve();
  
   //system("pause");
    return 0;
}

posted on 2010-06-21 22:49 田兵 阅读(46) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2020年9月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜