标签:斜率优化dp

2 篇文章

Luogu P2900 [USACO08MAR]Land Acquisition G 题解
Describe 题目链接 Farmer John 准备扩大他的农场,眼前他正在考虑购买 $N$ 块长方形的土地。 如果 FJ 单买一块土地,价格就是土地的面积。但他可以选择并购一组土地,并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 $3 \times 5$ 和一块 $5 \times 3$ 的土地,他只需要支付 $5 \tim…
Luogu P3648 [APIO2014]序列分割 题解
Describe 题目链接 你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次: 选择一个有超过一个元素的块(初始时你只有一块,即整个序列) 选择两个相邻元素把这个块从中间分开,得到两个非空的块。 每次操作后你将获得那两个新产生…