问题1：

有一个n*m的迷宫，有两种地块，’*’表示该地块走过2次以后会被破坏，’x’表示该地块走过1次后就被破坏，无法行走到被破坏的地块。左上角坐标为(1,1)，右下角坐标为(n,m)，每一次必须向上下左右四个方向之一走一步（不能原地停留）。给定起点和终点，问能否从起点走到终点并且使终点恰好被破坏。

•输入：

数据组数t

n m

n行迷宫

起点坐标

终点坐标

•输出：YES或者NO

•数据范围：t<=10,0<=n,m<=500

思路：

由题目可知只有‘*’和‘x'两种地块，也就是说从起点到终点一定有一条路可以走一边。则问题转换成了如何让终点一定被破坏。

分情况讨论：

1、终点为‘x'。则走一次就会被破坏，满足题目要求。

2、终点为’*’，则需要找一条路可以从终点走到终点。此时终点正好被走了两次。即从终点出发，是否有一条路，可以从终点走到终点。

讨论不能从终点走到终点的情况：

1、迷宫只有一行或一列，起点和终点都在这一行和一列上，此时没有路，输出‘NO'

2、除此之外都有路，输出‘YES'。

解题关键：

读懂题目的意思，可以简化思路。如此题从终点开始思考便很简单啦。

问题2：

•冰激凌由n种材料组成，每制作一份冰激凌需要每种材料各一份。每种材料单价为Vi元，现在小明手上每种材料有Wi份，且有M元。问小明最多做多少份冰激凌。

•1<=n<=100,1<=m<=1e12

•0<=Wi<=1e12

•1<=vi<=100

思路：

求最大化或最小化问题，可以转换成求是否的问题。

要满足以下条件：

问题的答案是单调的（如此题，小明如果可以做n份，那小明也可以做n-1份）

问题转变成求区间（a，b）找到小明可以做出和不可以做出的分界线mid

即是一个二分搜索的问题，每次判断isOK(mid)即小明可不可以做mid份冰淇淋。

解题关键：

原问题的转换，最大最小问题转变成是否问题。

问题3：

•n行，但固定只有3列，从第一行任意位置走到最后一行任意位置，每一次可以向下，左下，右下走。如果走到的格子为0，则当前分数取相反数。问分数最高多少分

•格子内的数值w，-10000<=w<=10000,1<=n<=10000

思路：

动态规划问题。

用两个二维数组dp1,dp2分别保存当前位置的最大值和最小值。

如果遇到0,最小值就有了变为最大值的可能性，同理最大值。