[動態規劃]OI練習題：打鼴鼠 mouse 解題報告

【問題背景】
鼴鼠是一種很喜歡挖洞的動物，但每過一定的時間，它還是喜歡把頭探出到地面上來透透氣的。

根據這個特點阿Q編寫了一個打鼴鼠的遊戲：在一個n*n的網格中，在某些時刻鼴鼠會在某一個網格探出頭來透透氣。你可以控制一個機器人來打鼴鼠，如果i時刻鼴鼠在某個網格中出現，而機器人也處於同一網格的話，那麼這個鼴鼠就會被機器人打死。而機器人每一時刻只能夠移動一格或停留在原地不動。機器人的移動是指從當前所處的網格移向相鄰的網格，即從座標為（i,j）的網格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四個網格，機器人不能走出整個n*n的網格。遊戲開始時，你可以自由選定機器人的初始位置。

【任務描述】

現在你知道在一段時間內，鼴鼠出現的時間和地點，希望你編寫一個程序使機器人在這一段時間內打死儘可能多的鼴鼠。

【輸入格式】

你將從文件input.txt中讀入資料，文件第一行為n（n<=1000）, m（m<=10000），其中m表示在這一段時間內出現的鼴鼠的個數，接下來的m行每行有三個資料time,x,y表示有一隻鼴鼠在遊戲開始後time個時刻，在第x行第y個網格里出現了一隻鼴鼠。Time按遞增的順序給出。注意同一時刻可能出現多隻鼴鼠，但同一時刻同一地點只可能出現一隻鼴鼠。

【輸入樣例】

2 2

1 1 1

2 2 2

【輸出格式】

輸出文件output.txt中僅包含一個正整數，表示被打死鼴鼠的最大數目。

【輸出樣例】

1

【運行限制】

運行時限：1秒鐘

【評分方法】

本題目一共有十個測試點，每個測試點的分數為總分數的10%。對於每個測試點來說，如果你給出的答案正確，那麼你將得到該測試點全部的分數，否則得0分。

【分析】
讀完題目，很明顯發現這是DP題目。我一開始寫了一種算法，開一個三維數組，表示第k秒走到(i,j)時所能最多打死的鼴鼠（鼴鼠好可憐～），後來發現這個會爆內存，遂改用滾動數組進行優化，就這樣，雖然我過了樣例，但是一Submit，悲劇了，3錯7超時～於是乎，我也不管他怎麼錯了，因為我放棄了這種算法，因為它太慢了，時間複雜度O（N^2*M），必然超時，只能另闢蹊徑了。

於是，我又想了一種狀態，當成區間動態規劃來想、來做。
設F[i]為打死第i個鼴鼠後的最大值， 於是就有了下面的狀態轉移方程：

F[i]=max{F[j]}+1 (1<=j<=i-1,同時需要判斷是否滿足： 從第j隻鼴鼠走到第i隻鼴鼠所需時間>=兩隻鼴鼠出現的時間差)

邊界條件：F[0]=0 （其實有沒有都無所謂了）
目標結果：Max{F[i]} (1<=i<=M)
空間複雜度：O(M)
時間複雜度：O(M^2)  由於M最大值為10000，所以恰好滿足要求（即時間複雜度不能超過這個數量級）

【我的代碼】（10組數據跑了3.6秒）
查看裸代碼 View the raw code

C++语言: Codee#25309

01 /*
02 *Problem: 動態規劃練習題   打鼴鼠 mouse
03 *Author: Yeefan
04 *Method: Dynamic Programming
05 *Website: http://blog.yeefanblog.tk/
06 *GTalk: zyfworks@gmail.com
07 *Twitter: @zyfworks
08 */
09 #include <cstdio>
10 #include <cstdlib>
11 #include <iostream>
12 using namespace std;
13
14 int N,M;
15 int Ans=0;
16
17 class MOUSE
18 {
19 public:
20     int x,y,time;
21     int value;
22     MOUSE()
23     {
24         value=0;
25     }
26 }P[10002];
27
28 int abs(int x)
29 {
30     return (x>0?x:-x);
31 }
32
33 bool check(MOUSE X,MOUSE Y)
34 {
35     int pos=abs(X.x-Y.x)+abs(X.y-Y.y);
36     int tim=abs(X.time-Y.time);
37     if(tim>=pos)
38         return true;
39     return false;
40 }
41
42 int main()
43 {
44     freopen("mouse.in","r",stdin);
45     freopen("mouse.out","w",stdout);
46     scanf("%d %d\n",&N,&M);
47     for (int i=1;i<=M;i++)
48     {
49         scanf("%d %d %d\n",&P[i].time,&P[i].x,&P[i].y);
50         int Max=0;
51         for (int j=1;j<=i-1;j++)
52         {
53             if(!check(P[j],P[i]))
54                 continue;
55             if(P[j].value>Max)
56                 Max=P[j].value;
57         }
58         P[i].value=Max+1;
59         if(P[i].value>Ans)
60             Ans=P[i].value;
61     }
62     printf("%d\n",Ans);
63     return 0;
64 }