信息学奥赛试题是如何炼成的？

《信息学奥赛试题是如何炼成的？》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、OLYMPIADININFORMATICS信息学奥赛试题是如何炼成的？合肥信息学辅导站张金苗合肥信息学辅导站www.hfoier.cn思维体操智力风暴引言l想当年国际赛IOI1994 “数塔问题”可是难倒了一批当年的大牛，现在可是很多人学习动态规划第一个例子；全国联赛NOIP2006“能量项链”可是全国赛NOI1995“石子合并”与大学计算机教材上经典动态规划例子“矩阵相乘”的有机结合。l难道是当年的那些题目太“菜”了吗？当然不是，因为我们不能用现在的眼光看那些时过境迁的事物，青少年信息学奥赛也是在不断

2、变化与发展中的，把握信息学奥赛题目变化与发展规律，就能够站在一个比较高的高度，解决好较难的问题。合肥信息学辅导站www.hfoier.cn思维体操智力风暴l同时，把握信息学奥赛题目的变化与发展，也是剖析、揣摩了出题者的想法和一般思路的过程，这对于学习者和教学者都是有益的，这又就是另一种角度的“换位思考”，也是更高层次的学习与教学。l以下通过一系列由浅入深、在各级各类信息学竞赛中出现的真题，阐述信息学奥林匹克竞赛“变化与发展”这个永恒主题，通过如下讨论，也不难看出，信息学奥赛试题是如何演变与炼就的。合肥信

3、息学辅导站www.hfoier.cn思维体操智力风暴Contents F题题目目原原型型算算法法拓拓展展增增加加决决策策多多样样性性增增加加控控制制点点增增加加线线程程增增加加数学调数学调料料合肥信息学辅导站www.hfoier.cn思维体操智力风暴一、题目原型l[题1]棋盘路径l有一个n*m的棋盘，左上角为(1,1)，右上角为(n,m)。有一颗棋子，初始状态为(1,1)，该棋子只能向右走或者向下走，问改棋子从(1,1)到(n,m)一共有几条路径？（中国象棋，走边）(1,1)(n,m)l输入：两个整数n

4、和m l输出：一个数，路径总数。合肥信息学辅导站www.hfoier.cn思维体操智力风暴[解题思路] l除左边界和上边界上的点的路径，为其上面点的路径同左边点路径之和。(1,1) (i1,j)(i,j1)(i,j)(n,m)l递推公式：f(i,j)=f(i1,j)+f(i,j1)l边界条件：f(1,1)=1l程序框架lf[1,1]:=1;lFor i:=1 to n dolfor j:=1 to n dolif i*j<>1 then f[I,j]:= f(i1,j)+f(i,j1);合肥信息学辅导站

5、www.hfoier.cn思维体操智力风暴Contents 题题目目原原型型F算算法法拓拓展展增增加加决决策策多多样样性性增增加加控控制制点点增增加加线线程程增增加加数学调数学调料料合肥信息学辅导站www.hfoier.cn思维体操智力风暴二、算法拓展l上题就是一个单纯的二维递推；增加策略选择就成为简单动态规划题了。l[题2]最小伤害l小可可站在一个N xN的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。l输入数据

6、：第一行输入一个正整数n。以下n行描述该矩阵。矩阵中的数保证是不超过1000的正整数。l输出数据：输出最小伤害值。l样例输入：l3 l1 3 3 l2 2 2 l3 1 2 l样例输出：l8 l数据规模：ln<=1000合肥信息学辅导站www.hfoier.cn思维体操智力风暴[解题思路] l很简单的DP，但需要注意边界的预处理。l状态转移方程：lf(i,j)=min{f(i1,j),f(i,j1)}+f(i,j)；l对边界的不同处理方法方面，大致有两种解法（以下代码状态复用本身的值的数组，没有为状态单

7、独开辟存储空间）：l方法一：预先处理好左边界和上边界la:array[1..1000,1..1000] of longint;(1,1) €€(n,m)合肥信息学辅导站www.hfoier.cn思维体操智力风暴lfor i:=2to n do lbegin la[i,1]:=a[i,1]+a[i1,1];{左边界处理}la[1,i]:=a[1,i]+a[1,i1]; {上边界处理}lend;lfor i:=2to n do {DP主体部分}lforj:=2 to ndo la(i,j)=min{a(i1

8、,j),a(i,j1)}+a(i,j)；合肥信息学辅导站www.hfoier.cn思维体操智力风暴l方法二：左边、上边各扩展一行，置上一个较大的数la:array[0..1000,0..1000] oflongint; (0,0)€€(n,m)lfor i:=1 tondo{边界情况预处理}lbeginla[i,0]:=1000001; la[0,i]:=1000001; lend; lfor i:=1 tondo{DP主体部分}lfor