题28。花店橱窗布置问题(IOI99试题)
假设想以最美观的方式布置花店的橱窗,有F束花,每束花的 花瓶1 花瓶2 花瓶3 花瓶4 花瓶5 品种都不一样,同时,至少有同样数量的花瓶被按顺序摆成一行, 杜鹃花 7 23 -5 -24 16 21 -4 10 23 花瓶的位置是固定的,并按从左到右,从1到V顺序编号,V是花 秋海棠 5 5 -4 -20 20 瓶的数目,编号为1的花瓶在最左边,编号为V的花瓶在最右边, 康乃馨 -21 花束可以移动,并且每束花用1到F的整数唯一标志.标志花束的整数决定了花束在花瓶中排列的顺序,即如果i 题29。2007年宁波高中组第3题--宝石 / 1996年提高组第3题--挖地雷 【问题描述】 在一处原始森林中，发现了N个藏有宝石的山洞，这N个山洞以1至N编号。某些山洞间可能会有通道相连，山洞间的通道是单向的，编号较小的山洞可以通过通道走至编号较大的山洞，编号较大的山洞不可以通过通道走至编号较小的山洞。你可以选择任意一个山洞进入，选择一条通道，进入下一个较大编号的山洞，…，最后从某个山洞出来，并获得所有经过的山洞中的宝石。从外面只能进入一次，然后从一个山洞至另一个山洞，直至走出山洞。现在告诉你每个山洞中的宝石数，以及山洞之间的通道情况，求最多能取得多少宝石？ 【输入】输入文件gem.in有若干个行数据。 第一行有两个整数n和m，分别表示山洞数和通道数，两数间以一个空格分隔。 第二行有n个整数，第一个数表示第一个山洞的宝石数,第二个数表示第二个山洞的宝石数,…，第n个数表示第n个山洞的宝石数。这n个数间互相以一个空格分隔。 以下m行，每行描述两个山洞间有一条从编号较小山洞通向编号较大山洞的单向通道。每一行的两个整数a和b,可能表示山洞a至山洞b间的单向通道，也可能表示山洞b至山洞a间的单向通道。a和b间有一个空格分隔。 【输出】 输出文件gem.out中只有一行，该行只有一个整数，表示最多能获得的宝石数。 【数据限制】 本题共有10组测试数据，每组10分，共100分， 对于所有的数据，获得的宝石总数不会超过2×109 30%的数据, 1≤n≤1000，0≤m≤10000 100%的数据, 1≤n≤20000，0≤m≤100000 【输入样例】 【输出样例】 5 6 27 10 8 4 7 6 1 3 1 2 1 4 3 4 3 5 4 5 题30。1999提高组第1题-拦截导弹 【问题描述】 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）：1）计算这套系统最多能拦截多少导弹；2）如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 【输入格式】输入文件missile.in只有一行数据,包括若干以空格分隔的正整数,表示来袭的导弹的高度. 【输出格式】输出文件missile.out应包括二行数据。 第一行只有一个正整数,表示最多能拦截的导弹数; 第二行也只有一个正整数,表示要拦截所有导弹最少要配备的系统数。 【输入样例】 389 207 155 300 299 170 158 65 【输出样例】 6 2 题31。2004年提高组第3题-合唱队形 【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2?，K，他们的身高分别为T1，T2，?，TK， 则他们的身高满足T1<... 【输入格式】输入文件chorus.in有2行数据。第一行是一个整数n(2<=n<=100)，表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 【输出格式】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 【输入样例】 8 186 186 150 200 160 130 197 220 【输出样例】 4 【数据规模】 对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。 题32。渡河 Problem iRabbit的国家被一条河流(河流是直的)分成南北两岸，南北两岸各有N个城市。北岸的每一个城市有一个唯一的友好城市在南岸，且他们的友好城市彼此不同。为了城市关系的发展，每对城市之间都想要开通轮渡。由于河面上常常有雾。iRabbit决定禁止船只航线相交。以避免发生安全事故。iRabbit希望能在保证安全的情况下，尽可能多地开通航线。由于N非常大（1<=N<=2004），所以必须用程序解决。iRabbit因为备战竞赛，所以十分繁忙，没有时间来编写程序，所以交给手下的TCR和sceoy解决。可是他们两个想了很久都没有想出答案，所以想请你来帮助解决。 Input 输入文件ferry.in的第1行有1个整数：N（1≤N≤2004）。接下来N行,每行两个数A,B。表示这一对友好城市与河源头的距离(不过100000)，其中A代表北岸城市、B代表南岸城市。 Output 输出文件ferry.out中只有一个整数。表示可以开通轮渡的最大线路数。 Sample Input Sample Output 7 4 22 4 2 6 10 3 15 12 9 8 17 17 4 2 a[I] b[I] 题33。最长公共子序列：勇闯黄金十二宫??射手宫-同济ACM第1108题 Problem “已知艾尔里斯和弟弟艾尔里亚的基因基本相同，由于基因表达起来不方便，所以就用n个数字来表示。(因为至今共发现100000种基因，所以每个数字都<=100000)兄弟之间的基因个数是相同的，就是说他们都有n个数字。且对于每个人，这n个数字互不相同。现在要求兄弟之间基因的最长公共部分。可以不连续。” Input 文件LCS.IN第1行，为n(1<=n<=100000) 下面2行，每行n个数字，表示了一个人的所有基因。 Output文件LCS.OUT一行，为他们两人基因的最长公共部分的长度。 Sample Input Sample Output 7 3 1 2 3 4 5 6 7 7 6 5 4 1 2 3 题38。管状矿藏duct.pas/duct.exe/duct.c/duct.cpp 【问题背景】A公司在南极大陆发现了一个稀有金属矿，该矿沿直线分布，共有n个点，每个点有一定量的矿藏。由于覆盖着冰块，不能从中间开采，只能从两头开采。由于该稀有金属的在地球上存量非常稀少，市场上价格越来越高，已知开采第一天的价格为1，第二天的价格为2，依次类推。A公司决定每天从两头选择一头开采出所有该点的矿藏。 【输入格式】输入文件duct.in包含以下内容：第一行:一个整数n，代表有n个矿点。第二行:n个整数，代表每个矿点的矿藏量。 【输出格式】输出文件duct.out包含一行，该行只有一个整数，代表开采出所有矿藏最多能得到的钱数。 【样例输入】 【样例输出】 4 21 1 2 3 1 【数据规模】 n<=1000，每点矿藏数不超过109，最多能得到的钱数<1012。 区域动规： 题13. 2003年提高组第3题--加分二叉树 【问题描述】 设一个n个节点的二叉树tree的中序遍历为(l,2,3,?,n),其中数字1,2,3,?,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数 若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,?,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分（2）tree的前序遍历 【输入格式】文件binary.in 第1行：一个整数n(n＜30)为节点个数。 第2行：n个用空格隔开的整数,为每个节点的分数(分数＜100）。 【输出格式】文件binary.out 第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 3 1 2 4 5 题14。2000年普及组第3题--乘积最大 问题描述： 今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生 诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1) 3*12=36 2) 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输入共有两行： 第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。 输出所求得的最大乘积（一个自然数）。 样例输入 4 2 1231 样例输出 62 题15。NOIP2003年普及组第2题--数字游戏（p2003_2.pas) 【问题描述】 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加, 相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。例如,对于下面这圈数字（n=4，m=2）： 2 当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为 ((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还 -1 4 是正数,对10取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。 -【输入】 1 3 输入文件GAME.in第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。 以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。 【输出】输出文件GAME.out有两行,各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。 【输入样例】