题意： 现在有 \(2n+1\) 个物品（\(n\le 300\)），体积分别为 \(-n,-n+1,\dots,-1,0,1,\dots,n\) ， 第 \(i\) 个物品有 \(a_i\) 个，求选出恰好 \(S\) 的总体积最多能选几个物品 。
第一步：缩小值域 。不妨设 \(\sum a_i>=S\)，否则将所有数取反 。
这时先选完所有的负数，然后不断选正数直至和恰好不超过 S ， 则此时的和应该属于 \([S-n,S]\)，值域范围被缩小了 。
第二步：缩小状态容易证明，从当前状态直至目标状态，必然存在一个操作序列 ， 使得在任意时刻当前的和属于 \([S-n,S+n]\) 。
第三步：缩小物品数又可以发现，如果存在两个时刻当前时刻的和相同，则这两个时刻之中的操作都是无用的，并且可以证明这一番无用操作一定会减小你所选出的物品数 。于是你最多进行 \(2n+1\) 次改变 。
每次改变至多变化 \(O(n)\)，因此 dp 值域 \(O(n^2)\) ， 时间复杂度即为 \(O(n^3)\) 。
【完全背包问题 —— 贪心优化 DP 范围】
推荐阅读
- 项目案例使用有效 解决ffmpeg的播放摄像头的延时优化问题
- C++算法之旅、02 从木棒切割问题领悟二分法精髓
- 教你如何解决T+0的问题
- 累加和为 K 的子数组问题
- 基于PL022 SPI 控制器 海思3516系列芯片SPI速率慢问题深入分析与优化
- 1 Redis—问题
- Android掌控WiFi不完全指南
- 完全看懂《冒死记录中国神秘事件》4部的高手进 冒死记录中国神秘事件
- 关于盗取东奥登陆账号处理问题 东奥登录
- 真正的解决英雄联盟fps值低的问题（5600g玩英雄联盟fps低)