英文原题 中文题译
大致题意:
奶牛需要补充多种维生素,农夫手头有N种药丸,每种可以补充一定维生素,每个药丸每天只能吃一颗,问最少需要多少药丸,且要求输出药丸字典序最小的排列。
经典的0-1背包问题,当然可以非递归回溯,不过这里可以直接递归。需说明的是注意递归的顺序,先选择吃,再选择不吃。如果吃了就行,那么不吃就不用再算了,因为只需要输出字典序最小的,而不吃的情况下继续搜索一者药丸数必定不会减少,二者字典序上升,故可以剪枝。同时注意在这里剪枝时需恢复数据。
大致题意:
奶牛需要补充多种维生素,农夫手头有N种药丸,每种可以补充一定维生素,每个药丸每天只能吃一颗,问最少需要多少药丸,且要求输出药丸字典序最小的排列。
经典的0-1背包问题,当然可以非递归回溯,不过这里可以直接递归。需说明的是注意递归的顺序,先选择吃,再选择不吃。如果吃了就行,那么不吃就不用再算了,因为只需要输出字典序最小的,而不吃的情况下继续搜索一者药丸数必定不会减少,二者字典序上升,故可以剪枝。同时注意在这里剪枝时需恢复数据。
/* ID: blackco3 TASK: holstein LANG: C++ */ #include <fstream> #include <memory.h> #define _max_vitamin_ 25 #define _max_feed_ 15 using namespace std; int require[_max_vitamin_], feeds[_max_feed_][_max_vitamin_] ; int n_vitamin, n_feed ; int trace[_max_feed_], uses[_max_feed_], n_need=_max_feed_ ; void get_need(int feed, int used) { if( feed>=n_feed || used>=n_need ) return ; int need_more=false ; for( int i=0; i<n_vitamin; i++ ){ require[i] -= feeds[feed][i] ; if( require[i]>0 ) need_more=true ; } uses[used++]=feed ; if( !need_more ){ if( used<n_need ) { n_need=used ; memcpy( trace, uses, sizeof(int)*used ); } for( int i=0; i<n_vitamin; i++ ) require[i] += feeds[feed][i] ; } else { get_need( feed+1, used ); for( int i=0; i<n_vitamin; i++ ) require[i] += feeds[feed][i] ; get_need( feed+1, --used ) ; } } int main() { ofstream fout ("holstein.out"); ifstream fin ("holstein.in"); fin >> n_vitamin ; for( int i=0; i<n_vitamin; i++ ) fin >> require[i] ; fin >> n_feed ; for( int i=0; i<n_feed; i++ ) for( int j=0; j<n_vitamin; j++ ) fin >> feeds[i][j] ; get_need(0,0); fout << n_need ; for( int i=0; i<n_need; i++ ) fout << " " << trace[i]+1 ; fout << endl; return 0; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 882英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1131英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1845郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1642英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1195英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 966英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1062英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1401英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 771英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 796英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 969英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1204英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 912英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1092英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 771英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1229英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1043英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 929英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1304英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 866英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ...
相关推荐
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
usaco2.1解题报告1
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
[USACO 1.1.4]破碎的项链.cpp
USACO全部译题 USACO Training Program Gateway
USACO_培训USACO_培训Ride.java-> Gift1.java->
2.1 Section 2.1 2.2 Section 2.2 2.3 Section 2.3 2.4 Section 2.4 3 Chapter3 3.1 Section 3.1 3.2 Section 3.2 3.3 Section 3.3 3.4 Section 3.4 4 Chapter4 4.1 Section 4.1 4.2 Section 4.2 4.3 Section 4.3 ...
USACO training 教程翻译合集(清晰明确)
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
One of the answer of the USACO training exercises.
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
自己前一段时间在坐usaco上的题目,一遍看题解,一遍做,做到第三章,就做不动了,发一些源程序和测试数据。
USACO题目中英文翻译,包含section1.3~1.5 2.1
usaco历年测试数据
usaco题库的Section2.1部分的castle问题解法源代码
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看