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)。该问题迎刃而解。 归纳本题:其实矩阵取数算法并不复杂,只要认真分析题目和给出的样例还 有提示,抓住要点,便可以轻松解题。



推荐相关:

NOIP2007普及组解题报告

NOIP2007普及组解题报告_IT/计算机_专业资料。NOIP2008普及组复赛试题解题报告 NOIP 2007 普及组解题报告 1、 奖学金 (scholar.pas/c/cpp) 、 【问题描述】 ...


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

2007年NOIP提高组第一题解题报告统计数字 - 1.统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n 个自然数,每个数均不超过 1500000000(1...


2007年NOIP提高组第二题解题报告字符串的展开

2007年NOIP提高组第二题解题报告字符串的展开 - 2.字符串的展开 (expand.pas/c/cpp) 【问题描述】 在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一...


守望者的逃离noip2007——解题报告

终于进入怨念的解题报告阶段了! 想必大家都玩过暴雪的经典《魔兽争霸 3 冰封...NOIP2007普及组初赛试题... 9页 免费 第十三届NOIP2007年普及... 8页 免费...

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