10599: Robots(II) ★★★★☆ 題組：Problem Set Archive with Online Judge 解題者：曹惟森 解題日期：2018年5月2日 題意：有一個N*M的矩陣，上面有些格子有垃圾，現在要求一個機器人從(1,1)出發抵達(N,M)，但是機器人只能向右或向下走，問最多能撿幾個垃圾?有幾種方法撿(不是路徑，而是撿了哪些垃圾)?並輸出字典序最小的方法。
題意範例： 6 7 6*7的矩陣 1 2 有垃圾的格子 1 4 4 1 4 4 4 7 5 2 6 6 0 0 沒垃圾了 1 2 題意範例： 6 7 6*7的矩陣 1 2 有垃圾的格子 1 4 4 1 4 4 4 7 5 2 6 6 0 0 沒垃圾了 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
把有垃圾的格子當成一個數列，並求其最長遞增子序列 (2D)要注意編號大的不能在編號小的左邊 解法範例： 解法： 把有垃圾的格子當成一個數列，並求其最長遞增子序列 (2D)要注意編號大的不能在編號小的左邊 解法範例： 首先假設終點有垃圾，如果其實沒有輸出時要扣掉。 從2開始，發現前面沒有可以接的，記錄皆在2後可以撿1個垃圾，撿1個垃圾為目前最佳解，共1組。 從4開始，發現可以接在2後面，記錄皆在4後可以撿2個垃圾，撿2個垃圾為目前最佳解，共1組。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
從22開始，發現前面沒有可以接的，記錄皆在22後可以撿1個垃圾，撿2個垃圾為目前最佳解，共1組。 從25開始，發現可以接在4後面，記錄皆在25後可以撿3個垃圾，撿3個垃圾為目前最佳解，共1組。 從28開始，發現可以接在25後面，記錄皆在28後可以撿4個垃圾，撿4個垃圾為目前最佳解，共1組。 從30開始，發現可以接在2後面，記錄皆在30後可以撿2個垃圾，撿4個垃圾為目前最佳解，共1組。 從41開始，發現可以接在25後面，記錄皆在41後可以撿4個垃圾，撿4個垃圾為目前最佳解，共2組。 從42開始，發現可以接在28後面，記錄皆在42後可以撿5個垃圾，撿5個垃圾為目前最佳解，共2組。 其實42並沒有垃圾，因此輸出時要扣掉。 輸出為:4 2 2 4 25 28 4代表最多撿4個垃圾 2代表2組解 2 4 25 28 為路徑的最小字典序