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 i=1;i<=n;i++){ cin>>a[i]; } dp[n]=1; for(i64 i=n-1;i>=1;i--){ for(i64 j=n;j>i;j--){ if(a[i]>=a[j]) dp[i]=max(dp[i],dp[j]+1); } } for(i64 i=1;i<=n;i++){ cout<<dp[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。
如果函数错了一个，或者符号写错了，就会错一大片。这里的测试点巨严。
#include<iostream> #include<iomanip> #include<algorithm> #include<queue> #define i64 long long using namespace std; i64 x=0,n=0,a[100005],dp[100005]; int main(){ while(cin>>x){ a[++n]=x; } i64 s[100005],top=0; s[0]=1e9; for(i64 i=1;i<=n;i++){ if(a[i]<=s[top]){ s[++top]=a[i]; }else{ i64 pos=upper_bound(s+1,s+top+1,a[i],greater<i64>())-s; s[pos]=a[i]; } } cout<<top<<endl; i64 sp[100005],tt=0; for(i64 i=1;i<=n;i++){ if(a[i]>sp[tt]){//如果是升序就入队 sp[++tt]=a[i]; }else{//如果更小，那么找比它更小的第一个，替换掉 i64 pos=lower_bound(sp+1,sp+tt+1,a[i])-sp; sp[pos]=a[i]; } } cout<<tt<<endl; return 0; }T2 打鼹鼠
P2285 [HNOI2004] 打鼹鼠 - 洛谷
这题出乎意料的好理解，真就是“会则易不会则难”的浓缩。
首先读题，我们得把距离和时间的关系想明白：两点坐标的差值绝对值之和需要小于时间之差（我们把这个距离叫曼哈顿距离，那个勾股定理的叫欧氏距离）。
然后定义dp[i]：打死第i只鼹鼠时，可以打死鼹鼠的最大数量。那么就用O(n^2)的思路，两层for循环去找就可以了。也就是：
if(dis<=t[i]-t[j]) dp[i]=max(dp[i], dp[j]+1);
然后每个dp的初始值都是1，因为打死自己就是1。
把dp的最大值找出来，就是打死鼹鼠的最大数量了。
#include<iostream> #include<iomanip> #include<algorithm> #include<queue> #define i64 long long using namespace std; i64 n,m; i64 t[10005],x[10005],y[10005],dp[10005],ans=0; int main(){ cin>>n>>m; for(i64 i=1;i<=m;i++) { cin>>t[i]>>x[i]>>y[i]; dp[i]=1; } //i表示选择打第i个可以打的只数 for(i64 i=1;i<=m;i++){ for(i64 j=1;j<i;j++){ i64 dis=abs(x[i]-x[j])+abs(y[i]-y[j]); if(dis<=t[i]-t[j]){ dp[i]=max(dp[i],dp[j]+1); } } ans=max(ans,dp[i]); } cout<<ans<<endl; return 0; }题解还有一个更复杂更朴素也更难的dp逻辑。
这一点就不写了喵。
T3 琪露诺
P1725 琪露诺 - 洛谷
这一题我自己是写出来了的，就是按照题意，后面的等于前面的+a[j]，取最大值即可。
#include<iostream> #include<iomanip> #include<algorithm> #include<queue> #define i64 long long using namespace std; i64 n,lt,rt; i64 a[1000005],dp[1000005]; bool s[1000005]; int main(){ cin>>n>>lt>>rt; for(i64 i=0;i<=n;i++) { cin>>a[i]; dp[i]=a[i]; } s[0]=1; for(i64 i=0;i<=n;i++){ if(s[i]==0) continue;//没有行走的权限 for(i64 j=i+lt;j<=i+rt;j++){ dp[j]=max(dp[i]+a[j],dp[j]); s[j]=1; } } i64 ans=-1e9; for(i64 i=0;i<=n;i++){ cout<<s[i]<<' '<<dp[i]<<endl; if(s[i]!=0){ ans=max(ans,dp[i]); } } cout<<ans<<endl; 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。那么加回来就是head=tail了。
如果后面的数比前面的数小一点，那这个也要入队，这是因为后来的数可能比前面的数还更小，所以这个数是有当top1的可能性的。当head坐标移动，也就是因为区间长度本身不够，而不是后面来的数据更大，就可以称霸了。所以整体感性地看下来，head和tail都是可能会移动的。
#include<iostream> #include<iomanip> #include<algorithm> #include<queue> #define i64 long long using namespace std; i64 n,lt,rt; i64 a[1000005],dp[1000005]; bool s[1000005]; int main(){ cin>>n>>lt>>rt; for(i64 i=0;i<=n;i++) { cin>>a[i]; dp[i]=-1e18; } dp[0]=a[0]; i64 head=1,tail=0,ans=-1e18; i64 q[100005]; for(i64 i=1;i<=n;i++){ i64 idx=i-lt; if(idx>=0){ //可达才可以入队 if(dp[idx]>-1e17) while(head<=tail&&dp[q[tail]]<=dp[idx]){ tail--; } q[++tail]=idx; } while(head<=tail&&q[head]<i-rt){ head++; } if(head<=tail){ dp[i]=a[i]+dp[q[head]]; } } for(i64 i=n-rt+1;i<=n;i++){ if(dp[i]>-1e17){ ans=max(ans,dp[i]); } } cout<<ans<<endl; return 0; }写在最后：
这一份帖子是我备战天梯赛（4月）之前就写好了的，当时计划说想把动态规划这一块都给写一遍。但真正执行起来还是颇有难度，不知怎么滴，过完天梯赛，鸽鸽鸽，搁到了现在，我再也没打过一题算法。
做的工作就是准备面试、准备软考，然后自己用unity写上了三国杀。我本来还想先AK猪国杀的，结果又没做到。
少年的心气是不可再生之物，莫过于此。
现在有一种觉得算法就是做题家大学版的味道了，而我无比地想知道，计算机软件的开发到底是怎么做到的，和这么不规范这么若秩的代码习惯是怎么搭边的。直到这个五月底，我把该做的事情都做完，就到了一个新的阶段了，也很难再去回头看来时的路了。
以后就没准就更推免帖子了呢？
