[問題]01背包的分堆變形題

[fatcat8127 (胖胖貓)]

先上題目：e900:交換紙牌遊戲

https://zerojudge.tw/ShowProblem?problemid=e900

題目要求和01背包的變形問題-分堆一樣，要求分成兩堆且數字和越接近越好。

但這個題目多了限制就是在最少的翻牌次數...。

這邊提供通過的程式碼：https://ideone.com/qQ5iL5

問題差異：

選某張卡片正面的點數時是加上差值且翻牌次數不變，否則必定選擇反面，

加上「負的差值」且次數多一，分堆問題時只要考慮選不選某個數字，

不選時狀態不變，但這題不選時因為加上「負的差值」狀態會改變。

狀態設定：

狀態改變時會有負數，陣列不能存取負的位置所以需要做偏移，

最糟糕的情況＝負最多時，每張牌的範圍是(-１２，１２)，牌數最多１０００張，

總和＝(-１２０００，１２０００) ... 陣列的空間要求。

base(偏移量)＝所有牌的負值總和。

初始狀態：用到的數字＝０(做完偏移後是 base)且該狀態下翻牌次數＝０

cnt[ 目前使用的陣列 ][ 偏移後的數字 ]= 最少的翻牌次數

狀態轉移：

根據第ｉ張牌，只需更新 pvt (上一次有紀錄到的數字)，避免重複紀錄這一次更新

到的狀態，只要檢查該格位置是否第一次更新。

   不翻：ｖ(新狀態)＝pvt+num[０][i]-num[１][i]且 翻牌次數不變

      cnt[now][v]=min(cnt[now][v],cnt[pre][pvt])

   翻牌：ｖ(新狀態)＝pvt+num[１][i]-num[０][i]且 翻牌次數多一

      cnt[now][v]=min(cnt[now][v],cnt[pre][pvt]+1)

輸出時從兩堆差值＝０，１(-1 or 1)... 依此類推直到找到第１個次數的狀態不是
INF 就是答案。



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.222.86.91 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1602146166.A.333.html
※ 編輯: fatcat8127 (61.222.86.91 臺灣), 10/08/2020 16:45:03
※ 編輯: fatcat8127 (61.222.86.91 臺灣), 10/08/2020 16:55:34
※ 編輯: fatcat8127 (61.222.86.91 臺灣), 10/09/2020 12:41:07
※ 編輯: fatcat8127 (61.222.86.91 臺灣), 10/09/2020 12:44:47
推 ucrxzero: 請問這比leetcode難嗎
推 ddavid: leetcode有簡單題也有難題，樓上你想問什麼
→ ucrxzero: 找工作需要寫這個嗎
推 ddavid: 看你找什麼工作，還有演算法題從來就不只是為了讓你背題到
→ ddavid: 時工作解一模一樣的問題
→ ddavid: 到時工作你不會直接看到背包問題，卻會用到解題思維以及動
→ ddavid: 態規劃、greedy、divide and conquer、tree、graph等等概
→ ddavid: 念，寫演算法題是為了讓你懂得怎麼自己思考應用這些概念
→ ddavid: 當然你可找個用不上解題思維的工作，但這個版就是解題版XD
推 ddavid: 看到你在別的版也問過leetcode的問題，也許我在Python以前
→ ddavid: 這篇拋磚的文章可以給你一點參考？XD #1UQl27Mt (Python)
推 ucrxzero: OK