洛谷 P7302 [NOI1998] 免费的馅饼

在这里插入图片描述

算法分析：

首先，最基础的想法是暴力 DP 复杂度 $O(n^2)$ 。设 $f [i]$ 表示在前 $i$ 个馅饼中，获得第 $i$ 个馅饼的最大得分。转移方程 $\max(f[i],f[j]+v[i])$ ，其中 $0 < j < i 0 且 a b s ( p [ i ] , p [ j ] ) ≤ 2 × ( t [ i ] − t [ j ] ) abs(p[i],p[j]) \leq 2 \times (t[i]-t[j]) 。这个转移复杂度是 O ( n 2 ) O(n^2) 。$

考虑把绝对值打开，式子就变为

{\begin{cases} p [i] - 2 \times t [i] \leq p [j] - 2 \times t [j] (p [i] \leq p [j]) \\ p [i] + 2 \times t [i] \geq p [j] + 2 \times t [j] (p [i] \geq p [j]) \end{cases}

{p [i] - 2 \times t [i] \leq p [j] -

相关阅读:
FFmpeg进阶: 截取视频生成gif动图
Task Flow使用指南之五：捕获异常
阿里P8晒1月工资条，看完真的狠狠扎心了…
深度学习（PyTorch）——flatten函数的用法及其与reshape函数的区别
分析SSH登录日志
工程企业管理软件源码-综合型项目管理软件
昇思25天学习打卡营第3天|onereal
[数据分析与可视化] 基于matplotlib和plottable库绘制精美表格
Kingbase备份与还原及表的约束(Kylin)
JavaScript防抖和节流的使用及区别

原文地址：https://blog.csdn.net/glorious_dream/article/details/126655955