尚未解答計算數學 Problem Solving- 01背包的分堆變形題
計算數學 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 就是答案。
--
0個答案
計算數學 Problem Solving- 01背包的分堆變形題
