英文原题
中文题译
这是个与日常生活相关的题。商场促销,把许多商品捆绑销售并优惠价格,一个精明的先生拿着老婆给的购物清单来买东西,他准备给自己存点私房钱,所以,他不打算为省钱买不需要的东西(如果是女士来,就会这样),为此他扫描了一遍所有的优惠活动,决定按最优方式来购买以节省最多的钱。
数据限制条件:商品种类最多999项,优惠活动最多999项,每项最多捆绑5件商品,优惠价总是比原价总和便宜。先生要买的物品最多5种,每种最多5件。
分析:虽然商品种类最多999项,但既然先生不准备买多余的东西,可认为只有最多5项,凡是优惠条目中包含不需要的商品的一律忽略。这是预处理过程,不妨设要买的商品就是1-5编号。每样最多5件,状态为6^5=7776,每个状态<a_i>(0<=i<5,0<=a_i<=5)有:
best<a_i>=min{best<a_i-b_j_i>+price_j|j为优惠方案,b_j_i为其中物品i的数量,price_j为其价格},
在优惠方案中加入原始报价(即只有一件物品数量为1)也作为一种方案,即不需特殊处理了。我倾向于用一维数组表示状态而不是5维,更具有一般性吧。
实现:
1. 在字符串缓冲区中读取内容时用sscanf不方便,改用isstream ;
2. DP过程中可以加点优化,对每个数,只要某个数值大于需要的相应位,就可跳过,不需完全搜索。
一次通过,很顺利。
中文题译
这是个与日常生活相关的题。商场促销,把许多商品捆绑销售并优惠价格,一个精明的先生拿着老婆给的购物清单来买东西,他准备给自己存点私房钱,所以,他不打算为省钱买不需要的东西(如果是女士来,就会这样),为此他扫描了一遍所有的优惠活动,决定按最优方式来购买以节省最多的钱。
数据限制条件:商品种类最多999项,优惠活动最多999项,每项最多捆绑5件商品,优惠价总是比原价总和便宜。先生要买的物品最多5种,每种最多5件。
分析:虽然商品种类最多999项,但既然先生不准备买多余的东西,可认为只有最多5项,凡是优惠条目中包含不需要的商品的一律忽略。这是预处理过程,不妨设要买的商品就是1-5编号。每样最多5件,状态为6^5=7776,每个状态<a_i>(0<=i<5,0<=a_i<=5)有:
best<a_i>=min{best<a_i-b_j_i>+price_j|j为优惠方案,b_j_i为其中物品i的数量,price_j为其价格},
在优惠方案中加入原始报价(即只有一件物品数量为1)也作为一种方案,即不需特殊处理了。我倾向于用一维数组表示状态而不是5维,更具有一般性吧。
实现:
1. 在字符串缓冲区中读取内容时用sscanf不方便,改用isstream ;
2. DP过程中可以加点优化,对每个数,只要某个数值大于需要的相应位,就可跳过,不需完全搜索。
一次通过,很顺利。
/* ID: blackco3 TASK: shopping LANG: C++ */ #include <iostream> #include <sstream> #include <string> #include <memory.h> using namespace std; const int _max_special_(1000), _max_type_(1000), _max_line_len_(256); const int _max_type_need_(5), _max_num_need_(5), _max_comb_(7776)/*as (5+1)^5 */; int n_type(0), n_tot_special(0), need[_max_type_], max_need(0); int nums[_max_type_], best[_max_comb_] ; struct t_special { int n_type, types[_max_type_need_], nums[_max_num_need_], price ; } specials[_max_special_+_max_type_need_], *ps_end=specials ; int main() { freopen("shopping.in", "r", stdin); freopen("shopping.out", "w", stdout); char lines[_max_special_][_max_line_len_+1] ; fgets( lines[0], _max_line_len_, stdin) ; sscanf( lines[0], "%d", &n_tot_special ) ; for( int i=0; i<n_tot_special; i++ ) fgets( lines[i], _max_line_len_, stdin ); memset( need, 0xff, sizeof(need) ); cin >> n_type ; for( int i=0; i<n_type; i++ ){ int type ; cin >> type >> nums[i] >> ps_end->price ; need[type] = i , ps_end->n_type=1, ps_end->nums[0] =1 , ps_end->types[0] = i, ps_end++ ; max_need = nums[i]>max_need ? nums[i] : max_need ; } istringstream iss ; for( int i=0; i<n_tot_special; i++ ){ iss.str(lines[i]), iss >> ps_end->n_type ; if( ps_end->n_type > n_type ) continue ; int ignore=false ; for( int j=0; j<ps_end->n_type; j++ ){ iss >> ps_end->types[j] >> ps_end->nums[j] ; if( need[ ps_end->types[j] ]==-1 ){ ignore=true ; break ; } ps_end->types[j] = need[ ps_end->types[j] ] ; } if( ignore ) continue ; iss >> ps_end->price ; ps_end++ ; } int n_comb=0, pow[_max_num_need_], cur_num[_max_type_need_] ; max_need++ ; /* to get 0..max_need*/ for( int i=0 ; i<n_type; i++ ){ n_comb = max_need*n_comb + nums[n_type-1-i]; cur_num[i] = 0 , pow[i] = i ? pow[i-1]*max_need : 1 ; } for( int i_comb=1; i_comb<=n_comb; i_comb++ ){ for( int pos=0; (++cur_num[pos])==max_need; pos++) cur_num[pos] = 0 ; int min_val=0x7fffffff ; for( t_special *pc=specials; pc!=ps_end; pc++ ){ int ignore=false, pre_comb=i_comb ; for( int it=0; it<pc->n_type; it++ ){ if( pc->nums[it] > cur_num[pc->types[it]] ){ ignore=true ; break ; } pre_comb -= pc->nums[it]*pow[pc->types[it]] ; } if( ignore ) continue ; min_val = min_val <= best[pre_comb] + pc->price ? min_val : best[pre_comb] + pc->price ; } best[i_comb] = min_val ; } cout << best[n_comb] << endl ; return 0; }
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 884英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1133英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1849郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1645英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1195英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 968英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1064英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1404英文原题 题意 一个 ... -
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 798英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 970英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1206英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1093英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 772英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1232英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1046英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 930英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1307英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 868英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ... -
USACO Training Section 3.2 Stringsobits
2010-01-18 01:04 990英文原题 中文题译 大意:求至多有L个1的第i个N位二进 ...
相关推荐
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
usaco的题目解答,包括题目和源代码以及简单的分析。适合广大acmer!
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
[USACO 1.1.4]破碎的项链.cpp
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 4.4 Section 4.4 5 Chapter5 5.1 Section 5.1 5.2 Section 5.2 5.3 Section 5.3 5.4 Section 5.4 5.5 Section 5.5
USACO全部译题 USACO Training Program Gateway
USACO_培训USACO_培训Ride.java-> Gift1.java->
第一行 优惠商品的种类数(0 ) 第二行..第 s+1 行 每一行都用几个整数来表示一种优惠方式 第一个整数 n 第一行: 两个用空格隔开的
USACO training 教程翻译合集(清晰明确)
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
One of the answer of the USACO training exercises.
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括