返回
机器人主页
ytz123@ytz123
镜像机器人。它周期性从北邮人论坛抓取新内容，并以机器人身份发帖、回帖。订阅它的具体帖子或回复以接收通知。
镜像机器人来源：Java允许发帖
0 · 29
已发帖 / 回帖
🔖
订阅它的发帖或回复
站点不再支持「绑定机器人整体」——避免多人共用同一 ID 时的通知冲突。请在下面的列表里按需订阅单条帖子或单层回复。
回复
“moon add,add oil！”
回复
“居然第一反应直接转k短路用Astar解决，太暴力了 对于每个状态dp[i][j]维护一个size为k的小根堆 然后dp[i][j]的堆，就直接把dp[i][j - 1]和dp[i - 1][j]两个堆里所有元素都加上v[i][j]扔进来 然后如果size超过了k就不断pop 结果就是dp[n][m]的堆里的元素 空间O…”
回复
“DP的话有个空间复杂度O(n^2)，时间复杂度O(n^3)的DP 你先把左右两个端点看成两个不可删去的石头，这样就有n+2个石头，标号为1,2,3...n+2 状态dp[i][j]代表到第i个石头，第i个石头不删去，并且前面已经删去了j个石头的情况下 前i个石头剩下的石头中的maximum of the minimum…”
回复
“直接二分答案吧，judge函数直接贪心应该没有问题，为啥要dp呢”
回复
“烧烤站！”
回复
“bd”
回复
“这不是O(N^3)的动态规划经典题吗，还有O(N^2)做法？”
回复
“第一题按照L/D从大到小排序，第二关键字是编号从小到大。证明的话你仅考虑i,j两个不同产品，i放在j前面更优的话列式，简化之后即可发现条件是li/di>lj/dj，显然该条件具有传递性。 第二题就直接bfs就行，或者把一条连通线路上的点当成一个点跑最短路，但是最坏情况下点和边能达到百万，堆优化dij也可能gg 第三题直…”
订阅本页面里的具体帖子或回复，会让对应的更新进入你的通知中心。