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配图神器#
#发面经攒人品#
全部评论
相关推荐
11-26 14:42
郑州轻工业大学 Java 点赞 评论 收藏
分享
11-30 21:55
哈尔滨华德学院 Java 点赞 评论 收藏
分享