09-20 14:27 中国科学技术大学 C++ 发布于浙江
关注
0920京东秋招笔试复盘
1.
题目大意：
给定一个长度为n的数字序列，将其划分为n/2个相邻的配对。要求以最小的修改次数，使得每个配对内的两个数字相同，且任意相邻配对的数字不同。
思路：
可抽象为经典的“相邻不同”动态规划模型。定义状态dp[i][d]为前i个配对，第i个配对选择数字d时的最小修改代价。
2.
题目大意：
在一个带节点权重的无向图中，寻找一条节点权重严格递减的最长路径。
解题思路：
根据节点权重（海拔）的大小关系，将原无向图中的边转化为有向边，从权重高的节点指向权重低的节点，从而构建一个有向无环图（DAG）。问题随即转化为求解该DAG上的最长路径#牛客AI配图神器#
#发面经攒人品#
题目大意：
给定一个长度为n的数字序列，将其划分为n/2个相邻的配对。要求以最小的修改次数，使得每个配对内的两个数字相同，且任意相邻配对的数字不同。
思路：
可抽象为经典的“相邻不同”动态规划模型。定义状态dp[i][d]为前i个配对，第i个配对选择数字d时的最小修改代价。
2.
题目大意：
在一个带节点权重的无向图中，寻找一条节点权重严格递减的最长路径。
解题思路：
根据节点权重（海拔）的大小关系，将原无向图中的边转化为有向边，从权重高的节点指向权重低的节点，从而构建一个有向无环图（DAG）。问题随即转化为求解该DAG上的最长路径#牛客AI配图神器#
#发面经攒人品#
全部评论
相关推荐
…..
查看7道真题和解析
点赞 评论 收藏
分享