作者fatcat8127 (胖胖貓)
看板Prob_Solve
標題[問題]01背包的分堆變形題
時間Thu Oct 8 16:36:02 2020
先上題目：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://webptt.com/m.aspx?n=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
1F：推 ucrxzero: 請問這比leetcode難嗎 10/18 18:19
2F：推 ddavid: leetcode有簡單題也有難題，樓上你想問什麼 10/21 09:06
3F：→ ucrxzero: 找工作需要寫這個嗎 10/21 10:29
4F：推 ddavid: 看你找什麼工作，還有演算法題從來就不只是為了讓你背題到 10/21 13:34
5F：→ ddavid: 時工作解一模一樣的問題 10/21 13:35
6F：→ ddavid: 到時工作你不會直接看到背包問題，卻會用到解題思維以及動 10/21 13:36
7F：→ ddavid: 態規劃、greedy、divide and conquer、tree、graph等等概 10/21 13:37
8F：→ ddavid: 念，寫演算法題是為了讓你懂得怎麼自己思考應用這些概念 10/21 13:38
9F：→ ddavid: 當然你可找個用不上解題思維的工作，但這個版就是解題版XD 10/21 13:40
10F：推 ddavid: 看到你在別的版也問過leetcode的問題，也許我在Python以前 10/21 13:44
12F：推 ucrxzero: OK 10/30 20:53