作者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/cn.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