• 題目

1. 要找到連續賭局最大可能贏到的錢，正代表獲勝，負責代表輸錢
2. 如果都是輸錢就印出Losing streak.

• 題目思路

  • 用dp記錄目前到此局能贏取最多錢的數目，與當格比，如果當格較大就從他開始取
  • ex: -1,2,3，紀錄到2的時候，如果取-1,2只能贏一塊錢，所以我們選擇只取2，該格的dp就紀錄2

• code

這題自己沒有想出來，我的dp還是有障礙

• https://github.com/william31212/uva/blob/master/uva10684/uva10684.cpp

留言與分享

• 題目

1. 人只能走往左走跟往下走，然後有幾個地方有障礙物，問說從左上走到右下有幾種方法

• 解題思路

  • 想了一下發現是dp，每一格都儲存從上面跟左邊總共有幾種方法，然後初始狀態就一種。
  • 右下角那格就答案，維護時建議用1-index比較好做

• code

  • https://github.com/william31212/uva/blob/master/uva825/uva825.cpp

留言與分享

寫題解讓自己可以review一次自己寫了甚麼…
幾百年沒刷題，程式能力依然爛QQ

• 題目

1. 有一段字串需要照他的規定做轉換，例如例題的G就要換成GNU’s
2. 給了原字串要問經過幾次轉換，他詢問的該個字母有幾個，最多轉換10000次
3. 每個答案要間隔一個換行

• 解題思路

  • 因為題目只是將一個字母轉換成字串，因此我們只需要計算每個字母在每次轉換的總數有幾個，不需照著做轉換。
  • 而題目有提到會出現的字元Ascii是從33~126之間，因此只要維護一個dp表格(我是直接開200)
  • 用tmp紀錄字母在轉換時會增加多少個不同的字母數量，接著看上一層狀態該個字母有多少就乘以他的幾倍，紀錄到下一格狀態
  • 如果紀錄每次狀態，陣列空間會太大，因此每次轉換過後，需要將結果狀態回灌給上一層，這樣只需要兩層的空間。

• code

  • https://github.com/william31212/uva/blob/master/uva10625/uva10625.cpp

留言與分享