今天建议放背景音乐《开始懂了》
来提每日一题
2024-11-04 10:45:03
蒲公英优质笔记激励计划2.0 转码 程序员 每天59秒拿下每日一题 北美求职 近期找工作现状 LeetCode 刷题 创作灵感
国区每日一题今日思路：
树状数组。借助树状数组点改区查。不包含相邻元素子序列的最大和等价于打家劫舍，记dp00,dp11分别为头尾均不选，头尾可选可不选的最大和，dp01和dp10同理推出。假设修改i处值为val，以i处将数组划分左右两部分l和r最大和有max(dp10(l)+dp11(r), dp11(1)+dp01(r))；即对于分界两边只能选择一边。使用树状数组存储四个dp状态，其余状态转移同理可得，最终答案为根处的dp11值，若l=r此时dp11为nums[l]和0的较大者，其余三个状态为0。树状数组一般开辟4倍的数组长度，这里输入限制不大使用无符号整型存储dp值。
国际站每日一题今日思路：
动态规划。将机器人和工厂按下标排序。记dp[i][j]为第i个工厂一共修理前j个机器人时最小花费。dp[i][j]可以从dp[i-1][j-k]转移，即第i个工厂修理k个机器人，根据贪心修理的k个机器人为j-k到j这样花费最少；花费为机器人与工厂i距离绝对差。初始化时每个工厂修0个机器人花费为0，最终答案为dp[m][n]。看到这点个赞吧[喝奶茶R]
0
阅读：0
