計算數學 Problem Solving- 01背包的分堆變形題

先上題目：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 就是答案。



--