作业帮acm:hdu2881,求一个不卡时的算法
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/19 15:11:46
acm:hdu2881,求一个不卡时的算法
在一个n*n的图上有m个点（相互之间距离就为汉密尔顿距离）,每个点都有一个最晚期限,开始的点可任意选择,问最多的访问点是多少.
很容易想到O(n^2)的DP算法,但m最大是10000,看见有30ms以下的算法,而且代码在1000B以下
这个是解题报告：
Problem J:Jack’s Struggle
简单的动态规划,类似于最长上升子序列的求解方法.
把所有任务按照完成时间排序,之后就是求最长上升子序列,这里的两个任务之间的大于关系定义为任务i 大于任务 j,当且仅当任务i的完成时间和任务j的完成时间之差不小于两任务完成地点之间的曼哈顿距离.
请问这种非直接的LIS如何实现?
在一个n*n的图上有m个点（相互之间距离就为汉密尔顿距离）,每个点都有一个最晚期限,开始的点可任意选择,问最多的访问点是多少.
很容易想到O(n^2)的DP算法,但m最大是10000,看见有30ms以下的算法,而且代码在1000B以下
这个是解题报告：
Problem J:Jack’s Struggle
简单的动态规划,类似于最长上升子序列的求解方法.
把所有任务按照完成时间排序,之后就是求最长上升子序列,这里的两个任务之间的大于关系定义为任务i 大于任务 j,当且仅当任务i的完成时间和任务j的完成时间之差不小于两任务完成地点之间的曼哈顿距离.
请问这种非直接的LIS如何实现?
lis有什么直接不直接的吗.这题关键是建立lis的模型和使用nlogn的lis算法
再问： 如果以任务的完成时间排序，长度为L的序列尾端怎样才是最优的呢，他这里面是曼哈顿距离
再答： 其实我还是不是很理解你的问题。。 不过我描述一下这题怎么建模吧，lis的算法就不多说了，上网查到处都是 常见的lis都是在一些数或者一些字母中求的，而此处则是在一堆mission中求，之所以mission也可以lis是因为所有的mission构成的集合是well ordered的（这是能够进行lis的关键），也就是说任何两个不同的元素之间都有一个序的关系，在这里，正如题解所说，定义mission a在mission b之后（也就是平常的大于）就是在a之后还能赶上时间完成b，这样一来整个问题就变成了lis问题 至于整个集合按什么顺序排成序列，答案显然是完成时间 因为完成时间在后是序在后的必要条件，按照完成时间排序才能使满足序先后关系的序列都成为当前mission列的子列，这样显然比其他排列得到的解更优
再问： 我的意思是这个，比如说对一个数组LIS，数组前4个数为1,3,8,2 当扫描到8是，dp[2]=3,dp[3]=8;扫描到2时，用2更新dp[2],那么这题里如果新扫描到的任务如果无法增加最大长度，如何证明他能更新其他较短长度dp值的最优性呢
再答： 原来你是对lis的思路有疑问啊。。简单证明一下好了 可以用数学归纳法证明任何时刻dp[i]都是当前长为i的子序列中末尾元素最小的序列的末尾元素（讲着挺绕口，就简称为最小的末尾元素好了） 当从原序列中取出第一个元素时，dp[1]显然是长为1的子序列的最小末尾元素 取完k个元素后dp仍然满足上述性质，则取a[k+1]时 假设按照nlogn的lis算法，a[k+1]能更新dp[L]，即a[k+1]dp[L-1]（这里把dp的初始值认为是正无穷大，L=0的情况另外讨论就是了，这里不说了） 接下来证明dp数组仍然保持上述性质 对于dp[1] to dp[L-1]，因为a[k+1]都比他们大，所以a[k+1]不可能称为长为1到L-1的子序列的最小元素，也就是说a[k+1]对dp[1]到dp[L-1]的值没有影响 对于dp[L]，若有比a[k+1]更小的末尾元素，该末尾元素一定不是a[k+1]，所以a[k+1]对这个更小的末尾元素是没有影响的，即在考虑完a[k]的时候dp[L]就应该等于这个更小的值了，也即dp[L]a[k+1]，所以“长为L的末尾元素小于a[k+1]的子序列”是不存在的，即dp[L=1]仍然保持性质 所以直到考虑完最后一个元素dp数组仍然保持这个性质，所以取最后一个非无穷大的元素对应的下标就是lis了 总的来说这个做法很直观。。不知道你是不是跟以当前位置为状态记录最小末尾元素的错误思路搞混了，注意这里还有一个状态——长度，所以是正确的
再问： 谢谢你写这么多啊，不过我的意思是针对这题的特殊性啊，这题的dp[i]是一个二元定义，（time,position),一个是发生时间，一个是在地图上的坐标。 解题报告里这样说的：“这里的两个任务之间的大于关系定义为任务i 大于任务 j，当且仅当任务i的完成时间和任务j的完成时间之差不小于两任务完成地点之间的曼哈顿距离。 ” 这个大小关系运用于增加现有最大长度这点我还是理解的过来的，但是更新更短的长度也能证明他的最优性吗
再答： 其实特殊性有什么关系呢，既然此题是lis没有问题，lis的算法是正确的没有问题，那么是任务也好其他什么也好有什么关系呢，证明还不都是一样的 如果你硬要不考虑lis的思路把这题当普通dp来做，那么把任务按照完成时间排成一列，dp[i][j]表示考虑到第i个元素时长度为j的末尾任务完成时间最早的任务序列的最后一个任务的完成时间，转移方程 dp[i][j]=a[i](a[i]dp[i-1][j-1]) 否则dp[i][j]=dp[i-1][j] 至于你说的那个问题，我觉得关键就是把序列长度当成状态了，要证明的话真的和上面的证明一样，想不出什么该多说的。。。
再问： 如果以任务的完成时间排序，长度为L的序列尾端怎样才是最优的呢，他这里面是曼哈顿距离
再答： 其实我还是不是很理解你的问题。。 不过我描述一下这题怎么建模吧，lis的算法就不多说了，上网查到处都是 常见的lis都是在一些数或者一些字母中求的，而此处则是在一堆mission中求，之所以mission也可以lis是因为所有的mission构成的集合是well ordered的（这是能够进行lis的关键），也就是说任何两个不同的元素之间都有一个序的关系，在这里，正如题解所说，定义mission a在mission b之后（也就是平常的大于）就是在a之后还能赶上时间完成b，这样一来整个问题就变成了lis问题 至于整个集合按什么顺序排成序列，答案显然是完成时间 因为完成时间在后是序在后的必要条件，按照完成时间排序才能使满足序先后关系的序列都成为当前mission列的子列，这样显然比其他排列得到的解更优
再问： 我的意思是这个，比如说对一个数组LIS，数组前4个数为1,3,8,2 当扫描到8是，dp[2]=3,dp[3]=8;扫描到2时，用2更新dp[2],那么这题里如果新扫描到的任务如果无法增加最大长度，如何证明他能更新其他较短长度dp值的最优性呢
再答： 原来你是对lis的思路有疑问啊。。简单证明一下好了 可以用数学归纳法证明任何时刻dp[i]都是当前长为i的子序列中末尾元素最小的序列的末尾元素（讲着挺绕口，就简称为最小的末尾元素好了） 当从原序列中取出第一个元素时，dp[1]显然是长为1的子序列的最小末尾元素 取完k个元素后dp仍然满足上述性质，则取a[k+1]时 假设按照nlogn的lis算法，a[k+1]能更新dp[L]，即a[k+1]dp[L-1]（这里把dp的初始值认为是正无穷大，L=0的情况另外讨论就是了，这里不说了） 接下来证明dp数组仍然保持上述性质 对于dp[1] to dp[L-1]，因为a[k+1]都比他们大，所以a[k+1]不可能称为长为1到L-1的子序列的最小元素，也就是说a[k+1]对dp[1]到dp[L-1]的值没有影响 对于dp[L]，若有比a[k+1]更小的末尾元素，该末尾元素一定不是a[k+1]，所以a[k+1]对这个更小的末尾元素是没有影响的，即在考虑完a[k]的时候dp[L]就应该等于这个更小的值了，也即dp[L]a[k+1]，所以“长为L的末尾元素小于a[k+1]的子序列”是不存在的，即dp[L=1]仍然保持性质 所以直到考虑完最后一个元素dp数组仍然保持这个性质，所以取最后一个非无穷大的元素对应的下标就是lis了 总的来说这个做法很直观。。不知道你是不是跟以当前位置为状态记录最小末尾元素的错误思路搞混了，注意这里还有一个状态——长度，所以是正确的
再问： 谢谢你写这么多啊，不过我的意思是针对这题的特殊性啊，这题的dp[i]是一个二元定义，（time,position),一个是发生时间，一个是在地图上的坐标。 解题报告里这样说的：“这里的两个任务之间的大于关系定义为任务i 大于任务 j，当且仅当任务i的完成时间和任务j的完成时间之差不小于两任务完成地点之间的曼哈顿距离。 ” 这个大小关系运用于增加现有最大长度这点我还是理解的过来的，但是更新更短的长度也能证明他的最优性吗
再答： 其实特殊性有什么关系呢，既然此题是lis没有问题，lis的算法是正确的没有问题，那么是任务也好其他什么也好有什么关系呢，证明还不都是一样的 如果你硬要不考虑lis的思路把这题当普通dp来做，那么把任务按照完成时间排成一列，dp[i][j]表示考虑到第i个元素时长度为j的末尾任务完成时间最早的任务序列的最后一个任务的完成时间，转移方程 dp[i][j]=a[i](a[i]dp[i-1][j-1]) 否则dp[i][j]=dp[i-1][j] 至于你说的那个问题，我觉得关键就是把序列长度当成状态了，要证明的话真的和上面的证明一样，想不出什么该多说的。。。