T1 导弹拦截P1020 [NOIP 1999 提高组] 导弹拦截 - 洛谷这题拆成两问先说第一问最多能拦截多少导弹也就是求最长的单调不增序列。O(n^2)的做法也就是暴力做法先开一层for_i循环从后往前遍历每个数然后再开一层for_j循环遍历到i的上一个就停止。里面做的就是如果a[i]a[j]那么dp[i]max(dp[i],dp[j]1)。初始值设定dp[n]1。你们可以通过这个cout来理解里面的运作逻辑。for(i64 i1;in;i){ cina[i]; } dp[n]1; for(i64 in-1;i1;i--){ for(i64 jn;ji;j--){ if(a[i]a[j]) dp[i]max(dp[i],dp[j]1); } } for(i64 i1;in;i){ coutdp[i]; }O(nlogn)的做法对于一个不理解的算法最直观的方式就是把过程写出来我也是这样理解整道题的。[389][389,207] //这两个都是if语句直接入栈即可。[389,207,155] //这两个都是if语句直接入栈即可。[389,300,155] //找到第一个小于等于300的并替换掉。[389,300,299] //找到第一个小于等于299的并替换掉。......[389,300,299,170,158,65]所以可以看出现在我们在干什么事从前往后读数据原先是从后往前读维护一个栈然后遇到比前面最小的元素更大不是大于等于的那么就不应该添加到栈顶而是替换一个元素。这个元素就是第一个比它更小元素所在的位置。怎么找这个元素就用二分查找的函数所以整体复杂度就降成遍历*二分查找O(nlogn)了。所以这么一顿操作后栈里有多少个元素就是最终答案。那么为什么这样是对的呢笔者水平有限无法证明我感觉大家也不是为了听懂证明吧但是我可以解释一个点有人觉得后面的元素去换掉栈前面的元素要是只换一半那么这个栈的序列不就乱了我的解释是用这题的例子如果只读到389,207,155,300那么栈的结果是[389,300,155]顺序是1、4、3没错但是这个300也可以当成207来看因为207小于300大于155。而如果到了题目的序列那么后面的栈变得越来越长了那么这个替换后的本身就是想要的序列了。所以你可以理解为栈没有新增元素就等于啥都没干。在这里就需要科普一下upper_bound和lower_bound它们都是二分查找函数但是前者是包含等于号后者不包含等于号。那么假设一个升序序列{0,1,3,5,5,5,7,9}要对标‘5’那么upper_bound是找“第一个大于五”也就是7所在的位置也就是a[6]lower_bound则是找“第一个大于等于五”也就是第一个5所在的位置a[3]。一个降序序列{0,9,7,5,5,5,3,1}此处0仅仅表示站位a[0]要对标‘5’那么upper_bound是找“第一个小于五”也就是3所在的位置也就是a[6]lower_bound则是找“第一个小于等于五”也就是第一个5所在的位置a[3]。降序用greater数据类型表示升序用less数据类型表示或者不填这个参数也是可以的。再说第二问这题需要用到一个结论Dilworth定理。最通俗的直接运用在这题的意思是最少下降子序列的覆盖数最长上升子序列的长度。更深刻的表达就是偏序集分解定理反正不学抽代我也看不懂。所以第二问理论上就是反过来变成升序序列了但是实际上我写代码的时候还思考到了上问疏忽的一个问题我到底该替换什么位置AI教我的是说让这个序列升的越慢越好下降地越慢越好。就比如一个序列[10,20,30]后面出来了个15那么我们就把20换成15这样的话这个栈就可能可以容纳下16 17 18这些数据了当然30还要再被更小的数替换掉这样来确定位置。上升越慢把第一个严格更大它的数据给换掉下降越慢把第一个小于等于它的数据给换掉。所以这题第一个是upper_bound第二个是lower_bound。如果函数错了一个或者符号写错了就会错一大片。这里的测试点巨严。#includeiostream #includeiomanip #includealgorithm #includequeue #define i64 long long using namespace std; i64 x0,n0,a[100005],dp[100005]; int main(){ while(cinx){ a[n]x; } i64 s[100005],top0; s[0]1e9; for(i64 i1;in;i){ if(a[i]s[top]){ s[top]a[i]; }else{ i64 posupper_bound(s1,stop1,a[i],greateri64())-s; s[pos]a[i]; } } couttopendl; i64 sp[100005],tt0; for(i64 i1;in;i){ if(a[i]sp[tt]){//如果是升序就入队 sp[tt]a[i]; }else{//如果更小那么找比它更小的第一个替换掉 i64 poslower_bound(sp1,sptt1,a[i])-sp; sp[pos]a[i]; } } coutttendl; return 0; }T2 打鼹鼠P2285 [HNOI2004] 打鼹鼠 - 洛谷这题出乎意料的好理解真就是“会则易不会则难”的浓缩。首先读题我们得把距离和时间的关系想明白两点坐标的差值绝对值之和需要小于时间之差我们把这个距离叫曼哈顿距离那个勾股定理的叫欧氏距离。然后定义dp[i]打死第i只鼹鼠时可以打死鼹鼠的最大数量。那么就用O(n^2)的思路两层for循环去找就可以了。也就是if(dist[i]-t[j]) dp[i]max(dp[i], dp[j]1);然后每个dp的初始值都是1因为打死自己就是1。把dp的最大值找出来就是打死鼹鼠的最大数量了。#includeiostream #includeiomanip #includealgorithm #includequeue #define i64 long long using namespace std; i64 n,m; i64 t[10005],x[10005],y[10005],dp[10005],ans0; int main(){ cinnm; for(i64 i1;im;i) { cint[i]x[i]y[i]; dp[i]1; } //i表示选择打第i个可以打的只数 for(i64 i1;im;i){ for(i64 j1;ji;j){ i64 disabs(x[i]-x[j])abs(y[i]-y[j]); if(dist[i]-t[j]){ dp[i]max(dp[i],dp[j]1); } } ansmax(ans,dp[i]); } coutansendl; return 0; }题解还有一个更复杂更朴素也更难的dp逻辑。这一点就不写了喵。T3 琪露诺P1725 琪露诺 - 洛谷这一题我自己是写出来了的就是按照题意后面的等于前面的a[j]取最大值即可。#includeiostream #includeiomanip #includealgorithm #includequeue #define i64 long long using namespace std; i64 n,lt,rt; i64 a[1000005],dp[1000005]; bool s[1000005]; int main(){ cinnltrt; for(i64 i0;in;i) { cina[i]; dp[i]a[i]; } s[0]1; for(i64 i0;in;i){ if(s[i]0) continue;//没有行走的权限 for(i64 jilt;jirt;j){ dp[j]max(dp[i]a[j],dp[j]); s[j]1; } } i64 ans-1e9; for(i64 i0;in;i){ couts[i] dp[i]endl; if(s[i]!0){ ansmax(ans,dp[i]); } } coutansendl; return 0; }但是不仅会TLE而且更重要的是对于全是负数的数据它没办法算因为dp[i]a[j]一定比dp[i]本身更小然而正确答案一定要经过这个dp[j]这一点。所以如果要避开这个就应该初始化为dp[i]-1e18然后再去遍历。那么我们逃课直接来看到本题的正解——滑动窗口滑动窗口我也一开始完全理解不了这个操作然后慢慢读慢慢读读了二十来分钟慢慢想清楚了q数组是模拟队列这个队列不是记录值而是记录下标head永远是对准队列首部也就是第一个位置的。那么这个队首所对应的下标q[head]指的是最大值下标就可以保证dp[q[head]]永远是最大值。所以如果后面准备来的数a[i-lt]比前面在队列的所有数都大那么就把前面所有的都给踢走就完事了。踢到什么情况为止tail比head小1。那么加回来就是headtail了。如果后面的数比前面的数小一点那这个也要入队这是因为后来的数可能比前面的数还更小所以这个数是有当top1的可能性的。当head坐标移动也就是因为区间长度本身不够而不是后面来的数据更大就可以称霸了。所以整体感性地看下来head和tail都是可能会移动的。#includeiostream #includeiomanip #includealgorithm #includequeue #define i64 long long using namespace std; i64 n,lt,rt; i64 a[1000005],dp[1000005]; bool s[1000005]; int main(){ cinnltrt; for(i64 i0;in;i) { cina[i]; dp[i]-1e18; } dp[0]a[0]; i64 head1,tail0,ans-1e18; i64 q[100005]; for(i64 i1;in;i){ i64 idxi-lt; if(idx0){ //可达才可以入队 if(dp[idx]-1e17) while(headtaildp[q[tail]]dp[idx]){ tail--; } q[tail]idx; } while(headtailq[head]i-rt){ head; } if(headtail){ dp[i]a[i]dp[q[head]]; } } for(i64 in-rt1;in;i){ if(dp[i]-1e17){ ansmax(ans,dp[i]); } } coutansendl; return 0; }写在最后这一份帖子是我备战天梯赛4月之前就写好了的当时计划说想把动态规划这一块都给写一遍。但真正执行起来还是颇有难度不知怎么滴过完天梯赛鸽鸽鸽搁到了现在我再也没打过一题算法。做的工作就是准备面试、准备软考然后自己用unity写上了三国杀。我本来还想先AK猪国杀的结果又没做到。少年的心气是不可再生之物莫过于此。现在有一种觉得算法就是做题家大学版的味道了而我无比地想知道计算机软件的开发到底是怎么做到的和这么不规范这么若秩的代码习惯是怎么搭边的。直到这个五月底我把该做的事情都做完就到了一个新的阶段了也很难再去回头看来时的路了。以后就没准就更推免帖子了呢
洛谷【动态规划2】线性状态动态规划 题解1-3 详细易懂不炫技
发布时间：2026/5/26 23:17:20
T1 导弹拦截P1020 [NOIP 1999 提高组] 导弹拦截 - 洛谷这题拆成两问先说第一问最多能拦截多少导弹也就是求最长的单调不增序列。O(n^2)的做法也就是暴力做法先开一层for_i循环从后往前遍历每个数然后再开一层for_j循环遍历到i的上一个就停止。里面做的就是如果a[i]a[j]那么dp[i]max(dp[i],dp[j]1)。初始值设定dp[n]1。你们可以通过这个cout来理解里面的运作逻辑。for(i64 i1;in;i){ cina[i]; } dp[n]1; for(i64 in-1;i1;i--){ for(i64 jn;ji;j--){ if(a[i]a[j]) dp[i]max(dp[i],dp[j]1); } } for(i64 i1;in;i){ coutdp[i]; }O(nlogn)的做法对于一个不理解的算法最直观的方式就是把过程写出来我也是这样理解整道题的。[389][389,207] //这两个都是if语句直接入栈即可。[389,207,155] //这两个都是if语句直接入栈即可。[389,300,155] //找到第一个小于等于300的并替换掉。[389,300,299] //找到第一个小于等于299的并替换掉。......[389,300,299,170,158,65]所以可以看出现在我们在干什么事从前往后读数据原先是从后往前读维护一个栈然后遇到比前面最小的元素更大不是大于等于的那么就不应该添加到栈顶而是替换一个元素。这个元素就是第一个比它更小元素所在的位置。怎么找这个元素就用二分查找的函数所以整体复杂度就降成遍历*二分查找O(nlogn)了。所以这么一顿操作后栈里有多少个元素就是最终答案。那么为什么这样是对的呢笔者水平有限无法证明我感觉大家也不是为了听懂证明吧但是我可以解释一个点有人觉得后面的元素去换掉栈前面的元素要是只换一半那么这个栈的序列不就乱了我的解释是用这题的例子如果只读到389,207,155,300那么栈的结果是[389,300,155]顺序是1、4、3没错但是这个300也可以当成207来看因为207小于300大于155。而如果到了题目的序列那么后面的栈变得越来越长了那么这个替换后的本身就是想要的序列了。所以你可以理解为栈没有新增元素就等于啥都没干。在这里就需要科普一下upper_bound和lower_bound它们都是二分查找函数但是前者是包含等于号后者不包含等于号。那么假设一个升序序列{0,1,3,5,5,5,7,9}要对标‘5’那么upper_bound是找“第一个大于五”也就是7所在的位置也就是a[6]lower_bound则是找“第一个大于等于五”也就是第一个5所在的位置a[3]。一个降序序列{0,9,7,5,5,5,3,1}此处0仅仅表示站位a[0]要对标‘5’那么upper_bound是找“第一个小于五”也就是3所在的位置也就是a[6]lower_bound则是找“第一个小于等于五”也就是第一个5所在的位置a[3]。降序用greater数据类型表示升序用less数据类型表示或者不填这个参数也是可以的。再说第二问这题需要用到一个结论Dilworth定理。最通俗的直接运用在这题的意思是最少下降子序列的覆盖数最长上升子序列的长度。更深刻的表达就是偏序集分解定理反正不学抽代我也看不懂。所以第二问理论上就是反过来变成升序序列了但是实际上我写代码的时候还思考到了上问疏忽的一个问题我到底该替换什么位置AI教我的是说让这个序列升的越慢越好下降地越慢越好。就比如一个序列[10,20,30]后面出来了个15那么我们就把20换成15这样的话这个栈就可能可以容纳下16 17 18这些数据了当然30还要再被更小的数替换掉这样来确定位置。上升越慢把第一个严格更大它的数据给换掉下降越慢把第一个小于等于它的数据给换掉。所以这题第一个是upper_bound第二个是lower_bound。如果函数错了一个或者符号写错了就会错一大片。这里的测试点巨严。#includeiostream #includeiomanip #includealgorithm #includequeue #define i64 long long using namespace std; i64 x0,n0,a[100005],dp[100005]; int main(){ while(cinx){ a[n]x; } i64 s[100005],top0; s[0]1e9; for(i64 i1;in;i){ if(a[i]s[top]){ s[top]a[i]; }else{ i64 posupper_bound(s1,stop1,a[i],greateri64())-s; s[pos]a[i]; } } couttopendl; i64 sp[100005],tt0; for(i64 i1;in;i){ if(a[i]sp[tt]){//如果是升序就入队 sp[tt]a[i]; }else{//如果更小那么找比它更小的第一个替换掉 i64 poslower_bound(sp1,sptt1,a[i])-sp; sp[pos]a[i]; } } coutttendl; return 0; }T2 打鼹鼠P2285 [HNOI2004] 打鼹鼠 - 洛谷这题出乎意料的好理解真就是“会则易不会则难”的浓缩。首先读题我们得把距离和时间的关系想明白两点坐标的差值绝对值之和需要小于时间之差我们把这个距离叫曼哈顿距离那个勾股定理的叫欧氏距离。然后定义dp[i]打死第i只鼹鼠时可以打死鼹鼠的最大数量。那么就用O(n^2)的思路两层for循环去找就可以了。也就是if(dist[i]-t[j]) dp[i]max(dp[i], dp[j]1);然后每个dp的初始值都是1因为打死自己就是1。把dp的最大值找出来就是打死鼹鼠的最大数量了。#includeiostream #includeiomanip #includealgorithm #includequeue #define i64 long long using namespace std; i64 n,m; i64 t[10005],x[10005],y[10005],dp[10005],ans0; int main(){ cinnm; for(i64 i1;im;i) { cint[i]x[i]y[i]; dp[i]1; } //i表示选择打第i个可以打的只数 for(i64 i1;im;i){ for(i64 j1;ji;j){ i64 disabs(x[i]-x[j])abs(y[i]-y[j]); if(dist[i]-t[j]){ dp[i]max(dp[i],dp[j]1); } } ansmax(ans,dp[i]); } coutansendl; return 0; }题解还有一个更复杂更朴素也更难的dp逻辑。这一点就不写了喵。T3 琪露诺P1725 琪露诺 - 洛谷这一题我自己是写出来了的就是按照题意后面的等于前面的a[j]取最大值即可。#includeiostream #includeiomanip #includealgorithm #includequeue #define i64 long long using namespace std; i64 n,lt,rt; i64 a[1000005],dp[1000005]; bool s[1000005]; int main(){ cinnltrt; for(i64 i0;in;i) { cina[i]; dp[i]a[i]; } s[0]1; for(i64 i0;in;i){ if(s[i]0) continue;//没有行走的权限 for(i64 jilt;jirt;j){ dp[j]max(dp[i]a[j],dp[j]); s[j]1; } } i64 ans-1e9; for(i64 i0;in;i){ couts[i] dp[i]endl; if(s[i]!0){ ansmax(ans,dp[i]); } } coutansendl; return 0; }但是不仅会TLE而且更重要的是对于全是负数的数据它没办法算因为dp[i]a[j]一定比dp[i]本身更小然而正确答案一定要经过这个dp[j]这一点。所以如果要避开这个就应该初始化为dp[i]-1e18然后再去遍历。那么我们逃课直接来看到本题的正解——滑动窗口滑动窗口我也一开始完全理解不了这个操作然后慢慢读慢慢读读了二十来分钟慢慢想清楚了q数组是模拟队列这个队列不是记录值而是记录下标head永远是对准队列首部也就是第一个位置的。那么这个队首所对应的下标q[head]指的是最大值下标就可以保证dp[q[head]]永远是最大值。所以如果后面准备来的数a[i-lt]比前面在队列的所有数都大那么就把前面所有的都给踢走就完事了。踢到什么情况为止tail比head小1。那么加回来就是headtail了。如果后面的数比前面的数小一点那这个也要入队这是因为后来的数可能比前面的数还更小所以这个数是有当top1的可能性的。当head坐标移动也就是因为区间长度本身不够而不是后面来的数据更大就可以称霸了。所以整体感性地看下来head和tail都是可能会移动的。#includeiostream #includeiomanip #includealgorithm #includequeue #define i64 long long using namespace std; i64 n,lt,rt; i64 a[1000005],dp[1000005]; bool s[1000005]; int main(){ cinnltrt; for(i64 i0;in;i) { cina[i]; dp[i]-1e18; } dp[0]a[0]; i64 head1,tail0,ans-1e18; i64 q[100005]; for(i64 i1;in;i){ i64 idxi-lt; if(idx0){ //可达才可以入队 if(dp[idx]-1e17) while(headtaildp[q[tail]]dp[idx]){ tail--; } q[tail]idx; } while(headtailq[head]i-rt){ head; } if(headtail){ dp[i]a[i]dp[q[head]]; } } for(i64 in-rt1;in;i){ if(dp[i]-1e17){ ansmax(ans,dp[i]); } } coutansendl; return 0; }写在最后这一份帖子是我备战天梯赛4月之前就写好了的当时计划说想把动态规划这一块都给写一遍。但真正执行起来还是颇有难度不知怎么滴过完天梯赛鸽鸽鸽搁到了现在我再也没打过一题算法。做的工作就是准备面试、准备软考然后自己用unity写上了三国杀。我本来还想先AK猪国杀的结果又没做到。少年的心气是不可再生之物莫过于此。现在有一种觉得算法就是做题家大学版的味道了而我无比地想知道计算机软件的开发到底是怎么做到的和这么不规范这么若秩的代码习惯是怎么搭边的。直到这个五月底我把该做的事情都做完就到了一个新的阶段了也很难再去回头看来时的路了。以后就没准就更推免帖子了呢
