《宜昌一中第四届NOIP模拟赛解题报告》由会员分享，可在线阅读，更多相关《宜昌一中第四届NOIP模拟赛解题报告（6页珍藏版）》请在金锄头文库上搜索。
1、 宜昌市一中第四届青少年奥林匹克信息学联赛暨哈利.波特模拟赛提高组试题题解NOM-NOIP2007-t4作者70（deathice）Stein (C|GatesMax)逃亡的准备(hallows.pas/c/cpp)Written by 70本题一看就看出是背包问题，如果在物品个数m较小的时候可以在传统背包加一层循环，循环m次，就可以轻松求解。可是m=v的物品可以转化为完全背包，这样题目的思路就清晰了。预处理时将物品分为可以用完全背包求解的和0/1背包求解的，两个背包求解可以在一个一维数组中实现。魔法石之恋(stone.pas/c/cpp)Written by 70这道题是一道模拟题，很多牛
2、人认为很难，其实很简单，但也要一定的小技巧。如果用一个二维数组来记录屏幕的状态，那么不仅麻烦而且时间复杂度很大。而且会出现一个问题，就是输入:8 52 4 1 1 1 1 1 1 正确答案是6 但是如果你用的2维数组记录的话 有可能答案是5，为什么？请自己画图分析!因为只有方块掉下来，并且只能在一开始决定横向位置。所以就可以用一个一维数组记录fi每个横向位置的当前高度，然后用贪心法模拟求解。配置魔药(medic.pas/c/cpp)Written by Stein (C|GatesMax)看完题目后，对题目分析可知，此题的最优解法就是动态规划。当然，因为有两个坩锅，所以明显是一道双进程动态规划
3、题目。因此，先用动态规划求解一个坩锅能达到的最大药效，把已用的药材去掉，再次动态规划的方法是不可行的！1分析最优子结构：数据备注：t1i表示第i种药材的起始时间t2i表示第i种药材的结束时间wi表示第i种药材的药效time表示总时间 n表示药材总数（为了让大家更好理解 先讲一种未优化的算法）设动态规划数组 dpijk 表示前i种药材放入两个坩锅，第一个坩锅达到时间j，第二个坩锅达到k时所能达到的最大药效。题目的解就是dpntimetime;因为要知道在time时刻两个坩锅的效益和，则需要用到它的子结构的最优值。分析子结构的最优值的取得条件：对于第i种药材，放入两个坩锅，有三种处理方法：1 把它
4、放入第一个坩锅；2 把它放入第二个坩锅；3 不放入任何坩锅对1： dpijk=dpi-1t1i-1k+wi; 条件：仅当j=t2i;对2： dpijk=dpi-1jt1i-1+wi; 条件：仅当k=t2i;对3： dpijk=max dpi-1jk, 无条件 dpij-1k, 条件 j0 dpijk-1, 条件 k0 因此 子结构dpijk的取值就是对1，2，3种状态的最大值即： dpijk=maxdpi-1t1i-1k+wi; 条件：仅当j=t2i; dpi-1jt1i-1+wi; 条件：仅当k=t2i;dpi-1jk, 无条件 dpij-1k, 条件 j0 dpijk-1, 条件 k0 2
5、解决后效性：为了解决后效性，在这里，当且仅当j=t1i或k=t1i时，药材才会被放入坩锅内，且保证了同一种药品不会在以后被多次放入或者是同时放入二个坩锅，当然，仅仅是这样还是不能保证能求出最优解，因为在计算过程中，结构会被刷新，因此对于结束时间较晚的药材，若在结束时间较前的药材先被计算，则较前的药材就以为价值小而不会被记录，因此就应该在动态规划之前将数据按结束时间t2i升序排序。因此，我们完美的消除了后效性。3.优化问题： 1时间复杂度的优化： 根据对称性，两个坩锅不计先后，且一摸一样，因此dpijk等价于dpikj，因此，在循环的时候可以令j=k;然后加几个判断即可。具体方法不再赘述，请自行
6、解决。 2空间复杂度的优化： 在求解的过程中 即：dpijk的值 只与 dpi-1的值有关，因此可以将数组降为2维 即：dpjk，具体方法不再赘述。可以看标程，标程有两个，一个是优化过的，一个是未经过优化的。因此，对于这道题目，近似最优时间复杂度为O(n3) 近似最优空间复杂度为O(n2)最大速度(maxv.pas/c/cpp)Written by 70首先要根据题意可以构图，将每一个点抽象成东南西北四个点,构造一个三维图。图构造好了就想算法，一开始会觉得是DIJKSTRA，但是有负权边就不可以用。我对Bellman的算法不太了解，但题目中有回路，应该也不行。后发现地图的边长小于30，就可以想
7、到搜索+剪枝来做。这样用一个数组记录出发点到这个点的最大速度，当再次搜到这个点的时候，如果搜到的值大于记录此点的最大速度，就更新记录，并继续向下搜；如果搜到的值小于等于记录此点的最大速度，就停止这次搜索。此外还有一个剪枝:可以在搜到的值小于（记录终点的最大速度+最多可以加的最大速度30），即再次搜索到达起飞点时不可能大于记录终点的最大速度。最后搜完之后比较起飞点四个方向的最大速度就可以了。此外，有很多Oiers不明白为什么连续两次转向要算做调头，因为如果在十字路口的时候，东西南北都有路可以连续两次转向这样就是调头，但是题目叙述中是必须在前，左，右都没路的时候才能调头，这么就会矛盾。所以加有此叙述，实际上连续两次转向是不可能的。 宜昌市一中信息奥赛组 2007第 2 页 共 6 页
