s****p
发帖数: 124 | 1 这道题:
Given string A representative a positive integer which has N digits, remove
any k digits of the number, the remaining digits are arranged according to
the original order to become a new positive integer.
Find the smallest integer after remove k digits.
N <= 240 and k <= N,
在网上看到一些答案, 说是每次删除剩下string里面第一个A[i] > A[i+1] 的数,重复K
次. 这对于每一步是局部最优解, 但我没想明白为什么这样做的是全局最优解.
这个怎么证明? | l****u
发帖数: 1764 | 2 利用sub optimal属性证明啊
删k个的最优解肯定是从删k-1的最优解基础上再删1位。否则如果还有更优的k-1解，那
么现在的最优就不是最优了
有点拗口，用数学表达式就更好理解
就是一个greedy问题 | s****p
发帖数: 124 | 3 不对啊. 比如考虑19752这个数,现在要删2位, 我们可以先删7得到1952,然后再删9得到
152. 这个1952不是删一位的最优解,但最后我们也得到了152的最优解.
就是说,全局最优解不一定需要从前面的最优解得出来. | a****l
发帖数: 30 | | s****p
发帖数: 124 | | l****u
发帖数: 1764 | 6 不矛盾啊 最优解152 肯定可以从最优解1752的来 不存在比1752更优的解，比1752 差
的解不用理会。每次都找最优解就不会漏掉最终最优解
：不对啊. 比如考虑19752这个数,现在要删2位, 我们可以先删7得到1952,然后再删9得
到152. 这个1952不是删一位的最优解,但最后我们也得到了152的最优解.
：就是说,全局最优解不一定需要从前面的最优解得出来.
【在 s****p 的大作中提到】
: 能够严格证明吗?
| w****e
发帖数: 586 | 7 可以，但懒得写详细。就说下大体证法。假设删k个数后的最优解是 N_k, 删k+1个数后
的最优解是 N_{k+1}. 你去比较 N_k 和 N_{k+1} 的首位不同的数字，可以证明N_k和N
_{k+1}唯一不同的就是这个数字（否则N_k和N_{k+1}中必有一个不是最优解，矛盾），
并且这个数字就是 N_k 里 “第一个A[i] > A[i+1] 的数”（否则N_{k+1}不是最优解
，矛盾）。然后数学归纳法从k=1开始推就行。这题要写清楚，有高中数学联赛省一等
奖水平。
【在 s****p 的大作中提到】
: 能够严格证明吗?
|
|
