题解

知识点提炼

动态规划优化

核心解题思路

思路1：利用特性(20pts)

对于前$20\%$数据，x_i始终为0，y_i为0或1。如果跳过一个点有可能少走$2$距离。

而跳过第一个点的跳过的花费为$1$，第二个点花费也为$1$，第三个点则花费为$2$，第四个点花费为$4$...故最多跳过两个点，跳更多的点并不会导致答案更优秀。

考虑暴力地枚举不跳过点、跳过一个点、跳过相邻的两个点和跳过不相邻的两个点的四种情况，时间复杂度为$O(n^2)$。

时间复杂度$O(n^2)$，期望得分$20$分。

思路2：01dfs(40pts)

对于$40\%$的数据，$n\leq 20$ ，考虑01dfs枚举$2$到$n-1$是否被删，在dfs终点计算当前01状态的花费，更新答案。

时间复杂度$O(n2^n)$。期望得分$40$分。

思路3：动态规划(50pts)

设立$f[i][k]$为到了i号点，且删了k个点的最小花费。则答案为$f[n][k]$取min。

对于$i$号点，枚举下一步去$j$号点，则会跳过$j-i-1$个点，$f[i][k]$状态可以转移至$f[j][k+j-i-1]$，所需花费为原花费$f[i][k]$、$i$到$j$的距离$dis(i,j)$、新增删点花费为删掉$k+j-i-1$个点的花费减去删掉$k$个点的花费。如果花费小于$f[j][k+j-i-1]$则可更新之。

时间复杂度$O(n^2)$。期望得分$60$分。

思路4：动态规划优化(100pts)

注意到$0\leq x_i,y_i\leq 10000$，故最坏情况下不跳过点的花费为$n*10000\sqrt2$，不超过$2*10^9$。

故跳过点的数量不会超过$31$次，否则至少存在一个方案所需花费更小：一个点也不跳过的方案。

所以我们可以在动态规划时，对于$i$号景点，只枚举后续的$40$个景点进行dp即可。

时间复杂度$O(n*40*40)$。期望得分$100$分。

本题易错点

有可能在$60\%$部分分时无法想到动态规划的优化错失满分。

有可能忽略$1$号点和$n$号点不允许跳过的限制，得出错误的结果。