tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 公务员考试 >>

NOIP2007提高组复赛试题解题报告三


4、【问题描述】 帅帅经常更同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每 个元素 aij 据为非负整数。游戏规则如下: 1. 每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有的元素; 2. 每次取走的各个元素只能是该元素所在行的行首或行尾; 3. 每次取数都有一个得分值,为每行取数的得分之和;每行取数的得分 = 被取 走的元素值*2i,其中 i 表示第 i 次取数(从 1 开始编号); 4. 游戏结束总得分为 m 次取数得分之和。 帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。 【输入】 输入文件 game.in 包括 n+1 行; 第一行为两个用空格隔开的整数 n 和 m。 第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开 【输出】 输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大的分。 【输入输出样例 1】 game.in game.out 2 3 82 1 2 4 3 4 2

【输入输出样例 1 解释】 第 1 次:第一行取行首元素,第二行取行尾元素,本次的氛围 1*21+2*21=6 第 2 次:两行均取行首元素,本次得分为 2*22+3*22=20 第 3 次:得分为 3*23+4*23=56。总得分为 6+20+56=82 【输入输出样例 2】 game.in game.out 1 4 122 4 5 0 5 【输入输出样例 3】 game.i n game.out 2 1 0 316994 96 56 54 46 86 12 23 88 80 43 16 95 18 29 30 53 88 83 64 67 【限制】 60%的数据满足:1<=n, m<=30,答案不超过 1016 100%的数据满足:1<=n, m<=80,0<=aij<=1000

对题目的分析:初看题目名为“矩阵取数”,其实仔细分析发现问题的关键 不在矩阵上。举例说明,有矩阵: a1,a2,a3……an b1,b2,b3……bn 有 N 列,但只有 2 行(这里考虑到书写,所以只列举了 2 行,大于 2 行也可以证明)
2 2 n

假设上面矩阵的最大得分取法是:a1*2+b1*2 + a2*2 +b2*2 ……+an*2 +bn* n 2 2 ,把这个算式变换一下,将 an 和 bn 的分开提取,结果变换为 a1*2+a2*2 …… +an*2n + b1*2+b2*22……+bn*2n。我们可以考察一下这个算式会发现:a1*2+a2*2 2 ……+an*2n 其实就是第一行 a1,a2,a3……an 的最大得分, b1*2+b2*22……+bn*2n 也是第二行 b1,b2,b3……bn 的最大得分。也就是说矩阵的最大得分其实是每一 行的最大得分之和,每一行的取数不会和其他行发生联系或冲突的。于是矩阵取 数最大得分问题就分解为行取数最大得分问题,只要求出每一行的最大得分,然 后求和,便可得出矩阵的最大得分。 再来考察一下单行取数问题的求解。首先,设函数 Maxgame(i,j)(i<j), 这个函数的功能是:求解一行 ai,a(i+1),a(i+2)……aj 的最大得分。那么 a1, a2,a3……an 的最大得分用这个函数来表示就是:Maxgame(1,n),那么这个 Max game(1,n)的值怎样求得呢?我们继续研究。由于取数的时候只能取行首数或是 行尾数,于是便有:Maxgame(1,n)=Max((a1*2+Maxgame(2,n)*2),(an*2+Maxgam e(1,n-1))), 1 到 n 的行最大得分要么等于取行首元素*2+从 2 到 n 的行的最 从 大得分*2;要么等于取行尾元素*2+从 1 到 n-1 的行的最大得分。所以,归纳 起来 Maxgame(1,n)就只有这 2 种可能性。再看看,此时的问题就被分解为了一 个相同的问题,只是数据规模小了 1:去掉了 a1 或 an,剩下的 a2,a3,……an 或 a1,a2,……a(n-1)成为新的待求最大得分的行。如此进行下取,当这一行只 剩下 2 个数时:ax,ay(x 必然等于 y-1,ax 和 ay 是相邻的 2 个数),则只需要 先取 min(ax,ay),最后一步取 max(ax,ay)。该问题迎刃而解。 归纳本题:其实矩阵取数算法并不复杂,只要认真分析题目和给出的样例还 有提示,抓住要点,便可以轻松解题。


推荐相关:

CCF NOIP2007年复赛提高组试题

CCF NOIP2007年复赛提高组试题_从业资格考试_资格考试/认证_教育专区。CCF NOIP...【输入输出样例 1】 game.in game.out 2 3 82 1 2 3 3 4 2 【输入...


NOIP2007提高组试题及解析

字符串长度不超过 100 解题思路:也是个水题,考察对语言的运用能力,字符串处理...NOIP2007提高组复赛试题 6页 免费 NOIP2007提高组试题 3页 免费 NOIP2007 初赛...


NOIP2008提高组复赛试题及题解

NOIP2008提高组复赛试题及题解_IT认证_资格考试/认证_教育专区。noip历届复赛试题...NOIP2006提高组复赛解题... NOIP2007提高组解题报告 NOIP2009提高组复赛题解 NOI...


历届noip提高组复赛试题

历届noip提高组复赛试题_学科竞赛_高中教育_教育专区。NOI’95 “同创杯”全国...[输入输出样例] d.in : 42 11 22 36 07 屏幕显示: 4 2003 年 20 / 56...


2007noip提高组复赛

3页 免费 2007noip 6页 免费 2007noip解题报告 7页 免费 2007NOIP初赛 8页 ...历届noip提高组复赛试题 56页 免费 1999-2009NOIP提高组复赛... 32页 免费 NO...


2008noip提高组复赛题解

2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组解题报告...已经过掉所有标准数据,以及 5 7 2 4 1 6 3 这组让很多贪心程序挂掉的数据...


2007年NOIP提高组第一题解题报告统计数字

2007年NOIP提高组第一题解题报告统计数字_电脑基础知识_IT/计算机_专业资料。1....NOIP2007提高组复赛试题... 2页 1下载券 NOIP2007提高组题解 2页 免费 NOIP...


NOIP2008提高组解题报告

NOIP2008普及组复赛试题... 14页 1下载券 NOIP2008提高组前三题解... 13页...NOIP2007提高组解题报告 12页 免费N​O​I​P​2​0​0​8​...


NOIP2013提高组复赛试题

NOIP2013提高组复赛试题_学科竞赛_高中教育_教育专区。全国信息学奥林匹克联赛(...【输入输出样例】 truck.in 4 1 2 3 3 1 1 1 3 24 33 11 3 4 3 ...


noip2007题解

noip2007题解_学科竞赛_高中教育_教育专区。解题报告 第一个题目 count [题目...[分析] 该题目实在是为了提高总分而用的。测试数据没有保证第一位不是'-' ...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com