【USACO 2.1】Healthy Holsteins

时间:2022-10-03 10:50:36
/*
TASK: holstein
LANG: C++
URL: http://train.usaco.org/usacoprob2?a=SgkbOSkonr2&S=holstein
SOLVE: con[i][j]为食物i含有维生素j的量,ned[i]为需要的维生素i的量
bfs,用二进制保存状态
*/
#include<cstdio>
#define N 30
int v,g,ned[N],con[N][N];
int now[N];
int l,r,q[];
bool vis[];
bool ck(int s){
//check whether state s is satisfied
for(int i=;i<=v;i++){
int tol=;
for(int j=;j<g;j++)
if((<<j)&s)
tol+=con[j][i];
if(tol<ned[i])return ;
}
return ;
}
void bfs(){
while(l<=r){
int k=q[l++];
if(ck(k)){
int num=;
for(int i=;i<g;i++)
if((<<i)&k)
num++;
printf("%d",num);
for(int i=;i<g;i++)
if((<<i)&k)
printf(" %d",i+);
puts("");
return;
}
for(int i=;i<g;i++)
if(!vis[k|(<<i)]){
q[++r]=k|(<<i);
vis[k|(<<i)]=;
}
}
}
int main(){
freopen("holstein.in","r",stdin);
freopen("holstein.out","w",stdout);
scanf("%d",&v);
for(int i=;i<=v;i++)
scanf("%d",&ned[i]);
scanf("%d",&g);
for(int i=;i<g;i++)
for(int j=;j<=v;j++)
scanf("%d",&con[i][j]);
bfs();
}

【USACO 2.1】Healthy Holsteins的更多相关文章

  1. 【Usaco 2009 Gold】JZOJ2020年9月19日提高B组T4 过路费

    [Usaco 2009 Gold]JZOJ2020年9月19日提高B组T4 过路费 题目 Description 跟所有人一样,农夫约翰以着宁教我负天下牛,休叫天下牛负我的伟大精神,日日夜夜苦思生财之 ...

  2. 【Usaco 2009 Gold】JZOJ2020年9月19日提高B组T3 头晕的奶牛

    [Usaco 2009 Gold]JZOJ2020年9月19日提高B组T3 头晕的奶牛 题目 Description 奶牛们发现,在农场里面赛跑是很有趣的一件事.可是她们一旦在农场里面不断地转圈,就会 ...

  3. 【Usaco 2009 Gold 】JZOJ2020年9月19日提高B组T2 电视游戏问题

    [Usaco 2009 Gold ]JZOJ2020年9月19日提高B组T2 电视游戏问题 题目 Description 农夫约翰的奶牛们游戏成瘾!本来FJ是想要按照陶叫兽的做法拿她们去电击戒瘾的,可 ...

  4. 【Usaco 2009 Silver】JZOJ2020年9月19日提高B组T1 音乐节拍

    [Usaco 2009 Silver]JZOJ2020年9月19日提高B组T1 音乐节拍 题目 Description FJ准备教他的奶牛弹奏一首歌曲,歌曲由N(1<=N<=50,000) ...

  5. 【USACO 2012 Open】Running Laps(树状数组)

    53 奶牛赛跑 约翰有 N 头奶牛,他为这些奶牛准备了一个周长为 C 的环形跑牛场.所有奶牛从起点同时起跑,奶牛在比赛中总是以匀速前进的,第 i 头牛的速度为 Vi.只要有一头奶牛跑完 L 圈之后,比 ...

  6. 【BZOJ】【1986】【USACO 2004 Dec】&sol;【POJ】【2373】划区灌溉

    DP/单调队列优化 首先不考虑奶牛的喜欢区间,dp方程当然是比较显然的:$ f[i]=min(f[k])+1,i-2*b \leq k \leq i-2*a $  当然这里的$i$和$k$都是偶数啦~ ...

  7. 【USACO 3&period;1】Stamps (完全背包)

    题意:给你n种价值不同的邮票,最大的不超过10000元,一次最多贴k张,求1到多少都能被表示出来?n≤50,k≤200. 题解:dp[i]表示i元最少可以用几张邮票表示,那么对于价值a的邮票,可以推出 ...

  8. 【USACO 3&period;1】Contact(01子串按出现次数排序)

    题意:给你一个01字符串,将长度为a到b之间(包含a.b)的子串按照出现次数排序.注意输入输出格式 题解:01子串对应一个二进制,为了区别11和011这样的不同子串,我们把长度也记录下来,官方题解是在 ...

  9. 【USACO 3&period;1】Score Inflation(完全背包)

    完全背包. http://train.usaco.org/usacoprob2?a=3Srffjlf4QI&S=inflate /* TASK:inflate LANG:C++ URL: */ ...

随机推荐

  1. &lbrack;Android Tips&rsqb; 23&period; How to fail&sol;stop Gradle task immediately if some conditions are not met

    throw new GradleException("conditions are not met") 参考 How to fail/stop task immediately i ...

  2. mata属性

    声明文档使用的字符编码:    <meta charset="utf-8" />声明文档的兼容模式:         <meta http-equiv=&quot ...

  3. Java-马士兵设计模式学习笔记-观察者模式-模拟Awt Button

    一.概述 Java 的Awt是 Observer模式,现用Java自己模拟awt中Button的运行机制 二.代码 1.Test.java import java.text.DateFormat; i ...

  4. using 关键字给类和名称空间指定别名

    1. using System; using System.Text; namespace DLL { public class Class1 { public void showStr() { Co ...

  5. FineUI上传控件

    文件上传 现在就简单多了,并且也漂亮多了,参考这个示例. 1: <ext:SimpleForm ID="SimpleForm1" BodyPadding="5px& ...

  6. 【重大bug】viewpager使用的时候加载数据应该在setOnPageChangeListener里加载

    [重大bug]viewpager使用的时候加载数据应该在setOnPageChangeListener里的onPageSelected里加载,我说怎么首页有数据,第二页就是空白,就是加载了但是数据不显 ...

  7. c&sol; c&plus;&plus; 多态

    多态 1.多态用途 为了代码可以简单的重复使用,添加一个功能时,接口不需要修改. #include <iostream> using namespace std; class A{ pub ...

  8. 随机重拍与抽样&lpar;random&lowbar;shuffle&comma;random&lowbar;sample&comma;random&lowbar;sample&lowbar;n&rpar;

    //版本一:使用内部的随机数生成器 template<class RandomAccessIterator> void random_shuffle( RandomAccessIterat ...

  9. 创建安全的基于HTTP的api应用接口

    #http://my.oschina.net/xiangtao/blog/196211 #要创建安全的基于HTTP的api接口,最重要的是要在服务端的进行请求的认证. #如何进行有效的服务端验证呢? ...

  10. Buffer Pool--锁定内存页

    锁定内存页在数据库中的优点和缺点: SQL Server 使用VirtualAlloc来分配内存,无内存压力时,SQL Server会尽可能地申请内存来缓存数据,当内存出现压力时,会出现缓存数据频繁地 ...