問題1：
有一個(gè)n*m的迷宮，有兩種地塊，’*’表示該地塊走過2次以后會(huì)被破壞，’x’表示該地塊走過1次后就被破壞，無法行走到被破壞的地塊。左上角坐標(biāo)為(1,1)，右下角坐標(biāo)為(n,m)，每一次必須向上下左右四個(gè)方向之一走一步（不能原地停留）。給定起點(diǎn)和終點(diǎn)，問能否從起點(diǎn)走到終點(diǎn)并且使終點(diǎn)恰好被破壞。
?輸入：
數(shù)據(jù)組數(shù)t
n m
n行迷宮
起點(diǎn)坐標(biāo)
終點(diǎn)坐標(biāo)
?輸出：YES或者NO
?數(shù)據(jù)范圍：t<=10,0<=n,m<=500
思路：
由題目可知只有‘*’和‘x'兩種地塊，也就是說從起點(diǎn)到終點(diǎn)一定有一條路可以走一邊。則問題轉(zhuǎn)換成了如何讓終點(diǎn)一定被破壞。
分情況討論：
1、終點(diǎn)為‘x'。則走一次就會(huì)被破壞，滿足題目要求。
2、終點(diǎn)為’*’，則需要找一條路可以從終點(diǎn)走到終點(diǎn)。此時(shí)終點(diǎn)正好被走了兩次。即從終點(diǎn)出發(fā)，是否有一條路，可以從終點(diǎn)走到終點(diǎn)。
討論不能從終點(diǎn)走到終點(diǎn)的情況：
1、迷宮只有一行或一列，起點(diǎn)和終點(diǎn)都在這一行和一列上，此時(shí)沒有路，輸出‘NO'
2、除此之外都有路，輸出‘YES'。
解題關(guān)鍵：
讀懂題目的意思，可以簡化思路。如此題從終點(diǎn)開始思考便很簡單啦。
問題2：
?冰激凌由n種材料組成，每制作一份冰激凌需要每種材料各一份。每種材料單價(jià)為Vi元，現(xiàn)在小明手上每種材料有Wi份，且有M元。問小明最多做多少份冰激凌。
?1<=n<=100,1<=m<=1e12
?0<=Wi<=1e12
?1<=vi<=100
思路：
求最大化或最小化問題，可以轉(zhuǎn)換成求是否的問題。
要滿足以下條件：
問題的答案是單調(diào)的（如此題，小明如果可以做n份，那小明也可以做n-1份）
問題轉(zhuǎn)變成求區(qū)間（a，b）找到小明可以做出和不可以做出的分界線mid
即是一個(gè)二分搜索的問題，每次判斷isOK(mid)即小明可不可以做mid份冰淇淋。
解題關(guān)鍵：
原問題的轉(zhuǎn)換，最大最小問題轉(zhuǎn)變成是否問題。
問題3：
?n行，但固定只有3列，從第一行任意位置走到最后一行任意位置，每一次可以向下，左下，右下走。如果走到的格子為0，則當(dāng)前分?jǐn)?shù)取相反數(shù)。問分?jǐn)?shù)最高多少分
?格子內(nèi)的數(shù)值w，-10000<=w<=10000,1<=n<=10000
思路：
動(dòng)態(tài)規(guī)劃問題。
用兩個(gè)二維數(shù)組dp1,dp2分別保存當(dāng)前位置的最大值和最小值。
如果遇到0,最小值就有了變?yōu)樽畲笾档目赡苄?，同理最大值?/p>
