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提高组复赛试题解题报告三.doc

NOIP2007提高组复赛试题解题报告三 - 4、【问题描述】 帅帅经常更同学玩

CCF NOIP2007年复赛提高组试题.doc

CCF NOIP2007年复赛提高组试题 - 全国信息学奥林匹克联赛(NOIP2007)复赛 题目名称 代号 输入文件 输出文件 时限 统计数字 count count.in count.out...

noip2017提高组复赛解题报告.doc

noip2017 提高组复赛解题报告 定期推送帐号信息学新闻,竞赛自主招生,信息

NOIP2007提高组解题报告.doc

NOIP2007提高组解题报告 - NOIP2007 提高组解题报告 1. 统计

NOIP2007_提高组_复赛试题.doc

全国信息学奥林匹克联赛(NOIP2007)复赛提高组 全国信息学奥林匹克联赛(NOIP2007)复赛提高组 1.统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了...

NOIP2007 提高组 复赛试题.pdf

字符串长度不超过 100 第3页 共6页 全国信息学奥林匹克联赛(NOIP2007)复赛 提高组 3. 矩阵取数游戏 (game.pas/c/cpp) 【问题描述】帅帅经常跟同学玩一个...

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

2007年NOIP提高组第一题解题报告统计数字 - 1.统计数字 (count.

NOIP2010提高组复赛试题及解题报告.doc

NOIP2010提高组复赛试题解题报告 - NOIP2010 提高组复赛试题解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软...

历届noip提高组复赛试题.doc

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

NOIP2007提高组初赛题目答案.pdf

2007 年 noip 提高组初赛试题一、 单项选择题 (共 10 题,每题 1.5 分,共...NOIP2007普及组解题报告 12页 1下载券 NOIP2007普及组复赛试题 5页 免费 NOIP...

NOIP2007 提高组复赛试题及参考程序(PASCAL).pdf

NOIP2007 提高组复赛试题及参考程序(PASCAL)_电子/电路_工程科技_专业资料。全国...【输入输出样例 1】 game.in game.out 2 3 82 1 2 3 3 4 2 【输入...

NOIP2007提高组解题报告.doc

NOIP2007提高组解题报告 - NOIP2007 提高组解题报告 1. 统计

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

2007年NOIP提高组第二题解题报告字符串的展开 - 2.字符串的展开 (ex

NOIP2007复赛提高组试题.pdf

第 1页 共 6页 全国信息学奥林匹克联赛(NOIP2007)复赛 提高组 1

2007noip解题报告.pdf

2007noip解题报告_环境科学/食品科学_工程科技_专业...noip2017普及组复赛解题... 7页 1下载券 解题报告...NOIP2007提高组试题及解... 12页 免费 ...

noip2007初赛提高组试题和答案.doc

noip2007初赛提高组试题和答案 - 第十三届全国青少年信息学奥林匹克联赛初赛试题 (提高组 Pascal 语言 二小时完成) ●● 全部试题答案均要求写在答卷纸上,写在...

2008noip提高组复赛题解.doc

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

NOIP2008提高组复赛试题及题解.doc

NOIP2008提高组复赛试题及题解 - 全国信息学奥林匹克联赛(NOIP200

NOIP2006提高组复赛解题报告.doc

NOIP2006提高组复赛解题报告 - 1、DP,f 表示合并区间内的珠子获得最

NOIP2014提高组复赛试题.pdf

NOIP2014提高组复赛试题 - CCF 全国信息学奥林匹克联赛(NOIP20

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