1、浅谈信息学中状态的合理设计与应用福建省福州第三中学 刘弈 引言l 在日常生活中，工作时间与工作数量、单位效率的关系可以用下面的这个式子来表达：工作时间 =工作数量 *单位效率引言l 在信息学中，程序的运行时间是由两个因素决定的，程序中所处理的状态的总数目和处理每个状态所花费的时间。程序运行时间 =状态总数 *单位效率 引言l 信息学中的状态总数有时隐藏着许多冗余状态。我们对状态的合理设计与应用不仅能优化的算法效率，还能够帮助编程人员理清思路，降低思维难度。例一 Square Root 状态分析合理地分析状态数目例二 Banal Tickets 状态优化对状态进行优化例三 Shoot Your
2、Gun 状态设计重新设计状态例三 Shoot Your Gunl 定义边平行于坐标轴的简单多边形为 矩形多边形 。l 已知在一个大的 矩形多边形 M中有两个小的矩形多边形 G和 T。 G边上的任意一点可以向其左上、左下、右上、右下四个方向发射出射线。射线在遇到 M的边时会发生光的镜面反射。l 求从 G边上的任意一点发出一条射线到 T所需要的最少反射次数。l 矩形多边形 最多包含 50条边，顶点坐标为整数在 0， 4000之内。下图左描绘出了一个例子，下图中描述了在特殊点时的反射规则。射线方向如下图右。l 题目中 G边上的任意一点都可以发射出射线。枚举？l 只需要处理整点和 1/2点即可。 题目分析l 使用普通的状态表示法，将每个点发射出的 4个方向分别做为 4个点，进行构图并使用最短路算法进行求解。l 这样的状态数是 O(n2)级别的，不能很好的解决此题。分析条件l 题目条件： 路线轨迹遵循光的传播路线 光是沿直线传播的，只有在遇到障碍物时才会发生反射 l 只有发生反射时，路线方向才会发生改变。也就是说，只有在边上才可能使方向发生变化。
