技术标签: 算法 # 洛谷 # dp 动态规划 数据结构 # codeforces
对于某个状态,可由一段连续区间转移,用单调队列维护实现O(1)转移
遗留题 P5858 「SWTR-03」Golden Sword
暴力dp d p i j dp_{i j} dpij 前i个,当前炼金锅有 j j j个物品的最大耐久度
j j j由 k ∈ [ j − 1 , j + s − 1 ] k \in[j-1,j+s-1] k∈[j−1,j+s−1] 转移 用单调队列优化枚举 k k k
P2254 [NOI2005] 瑰丽华尔兹
枚举每个时间段 k k k, d p k , i , j dp_{k,i,j} dpk,i,j表示前 k k k 个时间段,当前位置为 ( i , j ) (i,j) (i,j)时滑动的最大值 ,对于每个时间段 确定了 ( i , j ) (i,j) (i,j)由哪段区间转移,如果中途有障碍,则无法转移至之后滑动到的点(队列清空),对于之前的位置单调队列维护最佳转移点
P2569 [SCOI2010]股票交易
d p i , j dp_{i,j} dpi,j 第 i i i 天,手里还有 j j j 张股票,最多能赚的钱
枚举 i i i和 j j j,对于第i天,可以买卖股票,也可以什么都不干
什么都不干:直接由前一天转移 d p i , j = d p i − 1 , j dp_{i,j}=dp_{i-1,j} dpi,j=dpi−1,j
买卖:在 [ j − w , j − 1 ] [j-w,j-1] [j−w,j−1]这 w w w 天,对于 j j j 来说无效
所以从 i − w − 1 i-w-1 i−w−1 这一天转移
枚举 j j j ,然后对于枚举 k k k(买卖前有 k k k 张股票),可以使用单调队列维护 k k k 所在区间最优转移点
P2627 [USACO11OPEN]Mowing the Lawn G
最朴素做法: d p i , j dp_{i,j} dpi,j表示前 i i i 个数,连续选了 j j j 个数的最大和
第 i i i 个数有选或不选两种决策 时间复杂度 O(NK),但转移的时候不是由一段连续的区间转移
显然可以进行更优的状态设计,实际就是在这 n n n 个数中,选出几个数(和尽可能小),相邻两数的距离不超过 k + 1 k+1 k+1 ,那么枚举到第 i i i 个数时,能转移的状态区间范围可以缩小,且是一段连续的区间,能使用单调队列优化
d p i = m i n ( d p j + a i ) , j ∈ [ i − k − 1 , i − 1 ] dp_i=min(dp_j+a_i),j\in[i-k-1,i-1] dpi=min(dpj+ai),j∈[i−k−1,i−1]
2022南京 B
看到有修改,还有必建点的限制,不妨先丢到这两个额外的限制。
最简单版本:无修改,无必建点,然后就变成了一个很板的1D1Ddp,用单调队列优化
考虑加上必建点的限制:我们发现,如果我当前队列中要加进的点是必建点,那么在之后的转移,要保证这个点必选,队列中的所有点一定要全部弹出
考虑再加上修改的:先考虑最简单的,如果我当前修改的点是必建点,那么我只需要在原有答案上直接修改即可;但如果当前修改点不是必建点,我们考虑动态规划转移的一个贡献本质,假设当前修改点是 x x x , x x x 这个点最多只会对 [ x + 1 , x + k ] [x+1,x+k] [x+1,x+k] 产生直接的贡献,而 [ x + k , n ] [x+k,n] [x+k,n] 我们只会存在间接的贡献,也就是说,我们更新完 [ x + k , n ] [x+k,n] [x+k,n] 这些点后,后续我们的最小花费 g g g 是固定的(倒着dp预处理即可),那么对于更新后的 i ∈ [ x + 1 , x + k ] i \in [x+1,x+k] i∈[x+1,x+k] , a n s = m i n ( a n s , f [ i ] + g [ i ] − a [ i ] ) ans=min(ans,f[i]+g[i]-a[i]) ans=min(ans,f[i]+g[i]−a[i])
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
void yrzr(){
int n,k;
std::cin>>n>>k;
n++;
std::vector<int> a(n+1);
for (int i=1;i<n;i++){
std::cin>>a[i];
}
std::vector<int> must(n+1);
must[0]=must[n]=1;
for (int i=1;i<n;i++){
char ch;
std::cin>>ch;
must[i]=ch-'0';
}
std::deque<int> q;
q.push_back(0);
std::vector<ll> f(n+1);
for (int i=1;i<=n;i++){
while (!q.empty()&&i-q.front()>k){
q.pop_front();
}
f[i]=f[q.front()]+a[i];
// std::cout<<i<<" "<<f[i]<<"\n";
while (!q.empty()&&(must[i]==1||f[i]<f[q.back()])){
q.pop_back();
}
q.push_back(i);
}
while (!q.empty()){
q.pop_back();
}
std::vector<ll> g(n+1);
q.push_back(n);
for (int i=n-1;i>=0;i--){
while (!q.empty()&&q.front()-i>k){
q.pop_front();
}
g[i]=g[q.front()]+a[i];
while (!q.empty()&&(must[i]==1||g[i]<g[q.back()])){
q.pop_back();
}
q.push_back(i);
}
for (int i=0;i<=n;i++){
g[i]-=a[i];
// std::cout<<i<<" "<<f[i]+g[i]<<"\n";
}
int m;
std::cin>>m;
while (m--){
int p,v;
std::cin>>p>>v;
int use=a[p];
a[p]=v;
std::vector<ll> temp(k+5);
while (!q.empty()){
q.pop_back();
}
for (int i=std::max(0,p-k);i<=p-1;i++){
while (!q.empty()&&(must[i]==1||f[i]<f[q.back()])){
q.pop_back();
}
q.push_back(i);
}
// std::cout<<"\n";
for (int i=p;i<=std::min(p+k+1,n);i++){
temp[i-p]=f[i];
while (!q.empty()&&i-q.front()>k){
q.pop_front();
}
f[i]=f[q.front()]+a[i];
// std::cout<<f[i]<<" ";
while(!q.empty()&&(must[i]==1||f[i]<f[q.back()])){
q.pop_back();
}
q.push_back(i);
}
ll ans=1e18;
for (int i=p;i<=std::min(n,p+k+1);i++){
ans=std::min(ans,f[i]+g[i]);
}
// std::cout<<"\n";
std::cout<<ans<<"\n";
for (int i=p;i<=std::min(n,p+k+1);i++){
f[i]=temp[i-p];
}
a[p]=use;
}
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int T=1;
std::cin>>T;
while (T--){
yrzr();
}
return 0;
}
核心就是构造一个一次函数, y y y只与转移点有关, x x x只与一次转移点有关, k k k为x前系数,即斜率,剩下 b b b为 d p i dp_i dpi及其它杂项
由求 d p i dp_i dpi 的最小 / / /大 转换成求截距的最小(维护下凸壳)/大(维护上凸壳),维护时横坐标需由小到大,舍弃不可能选取的转移点,然后使直线与凸包相切,得到最优转移点
斜率变化单调时,找最优点可以用单调栈或单调队列优化至O(1)
斜率变化不单调时,找最优点用二分
P2365 任务安排
入门斜率优化
P3195 [HNOI2008]玩具装箱
经典分区间,按题意转移,整理式子斜率优化
P4072 [SDOI2016]征途
同样分区间问题,由方差的公式,考虑每多一个区间,对答案产生的贡献转移方程,难点在于式子的表达转换与如何选择合适的 d p dp dp含义,最后套一个斜率优化
P2120 [ZJOI2007] 仓库建设 超级hack数据 末尾的点可能没有货物,不需要建立仓库(即不需要对其划分区间)
规定物品只能往编号更大的地方运,转换为分区间,区间内的货物都送往区间右端点的问题。对于区间的内的每个店单独到右端点的距离,整体考虑转换为前缀和解决。整理式子,套斜率优化,找到最优的上一个区间右端点进行转移
P3628 [APIO2010] 特别行动队
区间划分板子,由题意易得转移方程,整理后套斜率优化
P5504 [JSOI2011] 柠檬
贪心的想,分出的区间若确定使用的贝壳大小 x x x,左右端点必须为 x x x 大小的贝壳,易证:由于区间个数无限制,如果不是,可以缩小当前区间,使其它大小贝壳分到其它区间产生贡献
d p i dp_{i} dpi代表当前区间右端点为 i i i,区间选择 s i s_i si 大小的贝壳 所得到的最大答案 ,枚举前一个状态 j j j 时:
第一步优化:存储 s j = = s i s_j==s_i sj==si的点
第二步优化:在存储的这些点的基础上用多个贝壳大小不同单调栈维护最佳相同贝壳大小的转移点。
CF 311B Cats Transport
将问题转换一下:将每只猫在某个位置出现的时间转换为在1这个点出现的时间,也就是预处理人走到某只猫位置 所耗费的时间
最后对每只猫在1这个点出现的时间进行排序
问题转换为分区间,一个区间对应一个铲屎官,可将区间右端点看做铲屎官出发时间,对答案产生的贡献即每个区间的数与右端点数的差:
∑ j i ( t i − t j ) \sum_j^i (t_i-t_j) ∑ji(ti−tj) 类似P2120 [ZJOI2007] 仓库建设 前缀和预处理
然后套斜率优化找到最优的前一个区间的右端点
CF631E Product Sum
设 d p i dp_{i} dpi表示 i i i数字移到某个位置后,序列的最大价值。
分类讨论 i i i移到 [ 1 , i − 1 ] [1,i-1] [1,i−1]和 [ i + 1 , n ] [i+1,n] [i+1,n],通过前缀和,枚举转移点 j j j 可 O ( 1 ) O(1) O(1)转移,复杂度为 O ( n 2 ) O(n^2) O(n2)。拆开式子发现可以进行斜率优化, Y = s u m i Y=sum_i Y=sumi, X = i X=i X=i, K = a i K=a_i K=ai,维护下凸壳,因为 a i a_i ai不一定单调所以用二分寻找最优转移点
当然也可以先对 a i a_i ai基数排序(因为 i i i对选取 j j j的范围没有影响),然后直接单调队列优化,复杂度 O ( n ) O(n) O(n)
CF1179D Fedor Runs for President
树上斜优
新添加一条边产生的贡献就是经过这条边的路径条数,首先分析哪些点对可以经过这条路径,比如当前增加一条路径1-2,那么3-5能经过,3-4不能经过
所以贡献式子为 ∑ s x ∗ ( n − s x ) 2 \sum {s_x*(n-s_x)} \over 2 2∑sx∗(n−sx) s x s_x sx即以 x x x为一个根,不向环上扩展的子树大小,化简式子:
n 2 − ∑ s x 2 2 n^2-\sum {s_x}^2 \over 2 2n2−∑sx2
因此我们只需要找到 s x 2 s_x^2 sx2的最小值即可
令 d p u dp_u dpu为在 u u u子树内,选取一个儿子的一条链,这条链的 ∑ s x 2 \sum {s_x}^2 ∑sx2最小值
分类更新答案 ∑ s x 2 \sum {s_x}^2 ∑sx2:
1. u u u为新增路径端点,那么 ∑ s x 2 \sum {s_x}^2 ∑sx2 就为 m i n ( d p v + ( n − s z v ) 2 ) min(dp_v+(n-sz_v)^2) min(dpv+(n−szv)2)
2. u u u为新增路径的经过点,那么 ∑ s x 2 \sum {s_x}^2 ∑sx2 就为
m i n ( d p v 1 + d p v 2 + ( n − s z v 1 − s z v 2 ) 2 ) min(dp_{v_1}+dp_{v_2}+(n-sz_{v_1}-sz_{v_2})^2) min(dpv1+dpv2+(n−szv1−szv2)2)
d p u dp_u dpu的转移也很好写,它的本质就是转移一条链,初始化 d p u = s z u 2 dp_u=sz_u^2 dpu=szu2,然后在选择儿子时取最小值 d p u = m i n ( d p v + ( s z u − s z v ) 2 ) dp_u=min(dp_v+(sz_u-sz_v)^2) dpu=min(dpv+(szu−szv)2)
对于2转移,需要O(n^2),拆开转移式,发现可以进行斜率优化,需要注意的是,要让 e u e_{u} eu数组的儿子以 s z v sz_v szv从小到大排序
文章浏览阅读1.1k次。解决方法:重新创建certificate证书,上传本机的CSR证书认证文件3.Production(一般只能创建3次)选中:App Store and Ad Hoc 然后下载证书到桌面,双击安装后,重新发布app到App Store中即可 转载自:https://blog.csdn.net/yishengzhiai005/article/details/7863..._has one ios distribution but its private key is not installed
文章浏览阅读1.1k次。//利用属性分开PrimitivePrimitive Split 节点中Attribute 设置为split 。Wrangle中代码为: f@split = @ptnum>10?1:4; 比较程序化的是利用Houdini 的Paint 节点,给物体描绘上颜色,然后利用颜色属性把Primitive 分开//曲线(在Vex中实现Carve节点的功能)最近在做植物生长的r..._houdini adjustprimlength
文章浏览阅读5.6k次,点赞9次,收藏46次。Qt+OSG/osgEarth跨平台编译(Windows、linux、macos)。用Qt Creator组装各个库,实现一套代码、一套框架,完成跨平台编译第三方库;实现一套代码、一套框架,完成跨平台编译OSG核心库、工具库、插件库及内省库,osgEarth核心库及插件库。_qt osgearth
文章浏览阅读184次。 一、路由器接口管理端口 路由器包含用于管理路由器的物理接口。这些接口也称为管理端口。与以太网接口和串行接口不同,管理端口不用于转发数据包。最常见的管理端口是控制台端口。控制台端口用于连接终端(多数情况是运行终端模拟器软件的 PC),从而在无需通过网络访问路由器的情况下配置路由器。对路由器进行初始配置时,必须使用控制台端口。 另一种管理端口是辅助端口。并非所有路由器..._路由器接口负责接收和转发数据包,接口类型有
文章浏览阅读1.4w次,点赞12次,收藏32次。英文名称中文名称图片BUTTON复位开关Resistors电阻crystal晶振_proteus 8 professional元器件对照表
文章浏览阅读1k次。gcc -o pcieinject ./pcietest_hypcie.c ./pcietest_parse.c ./pcietest_pcie.c ./pcietest_pcieaer.c smnlib/hygon_smn.c -O0 -g -Wall -D LITTLEENDIAN_CPU -I comlib -I pcilib -I smnlib -L ./pcilib/lib -Wl,-B..._pciutils
文章浏览阅读1.2w次,点赞16次,收藏99次。使用C++ 完成LR(0)的语法分析器由于最近学校里在学习编译原理,而且要求实现语法分析器,于是我用了几天的时间搞明白了语法分析器的原理并且将其实现了。由于编者还是本科生而且还在学习中,因此出现什么错误请各位指点。语法分析器的步骤为:读入单词序列读入语法规则构造基于该语法的Clousure(项目集规范族)集合基于上一步构造所有规范句型活前缀的DFA根据这个DFA来构造Action表..._c++lr0
文章浏览阅读570次。转载请注明原文地址:https://www.cnblogs.com/ygj0930/p/10826037.html一:XML文件中定义记录 XML中定义记录: 每个<record>元素有两个基本属性id和model,并且包含为每列分配值的<field>元素。如前所述,id属性对应于记录的外部标识符,模型属性对应于要写入..._odoo xml调用后台函数
文章浏览阅读3.3w次,点赞3次,收藏41次。我们知道,LTE是一个和WCDMA、GSM类似的术语,指的是移动通信的一种技术体系。不过和WCDMA、GSM的命名方式又不太一样,从WCDMA我们可以看出所采用的关键技术,从GSM我们可以看到应用场合,从LTE的命名中,似乎看不出技术特点和应用场合,是一种玄妙的命名方式。一说到LTE,就会想到4G。移动通信技术经历了1G、2G、3G、4G,到现在的5G,分别表示的是第一、二、三、四、五代移动通信系统,每一代都有各自的主流移动通信技术。目前,GSM和WCDMA可以当之无愧地称为2G和3G的主流移动通信技术。_lte标准
文章浏览阅读10w+次,点赞123次,收藏722次。anaconda 可以使tensorflow的安装变的简单昨天tensorflow 开发者大会刚开完,会上发布了关于 TensorFlow 2.0,TensorFlow Lite,TensorFlow.js,Swift for TensorFlow,TFX 等产品生态体系的最新更新和首次发布的内容,2019年任会支持tensorflow1.x,但是我们相信,版本的升级会带来易用性和使用性能的提升......_couldn't get ptxas version string: internal: couldn't invoke ptxas.exe --ver
文章浏览阅读1.9k次,点赞58次,收藏48次。软件安全复习(恶意代码部分)_bot是什么恶意代码
文章浏览阅读764次。注释.ssh config 文件中的#ProxyCommand connect -H 127.0.0.1:15732 %h %p_proxycommand connect -h 127.0.0.1:15732 %h %p