主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
L·篮球队招新
最后更新于 2025-07-31 09:53:18
作者
xixihaha2021
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
# [L·篮球队招新](https://183.250.108.194:500/OnlineJudge/problem_show.php?id=2714) ## 题意简述 给定一个非负整数列，每次操作可以将任意相邻两项合并为其差的绝对值。求最后剩余元素的最值。 ## 思路简述 典型的区间 DP，若设 $f_{l,r}$ 表示区间最大值，则不满足最优子结构的性质，因此考虑增加一维，即设 $f_{l,r,k}$ 表示区间内是否可能出现 $k$，`bitset` 维护位运算优化时间。不难写出转移方程 $f_{i,j} \gets f_{i,j}\ \text{or}\ ([f_{i,k,t}=1]\cdot (f_{k+1,j} >> t))\ \text{or}\ ([f_{k+1,j,t}=1]\cdot (f_{i,k} >> t))$。式中 `>>` 为右移运算。则最值即最后一个 `1` 和第一个 `1`。依照上述转移即可。 时间复杂度 $O(\dfrac{n^4 \cdot \max_{i=1}^n a_i}{\omega})$，空间复杂度 $O(n^2\max_{i=1}^n a_i)$。
正在渲染内容...
点赞
0
收藏
0
