2.17题型总结

递推四题讲3题

划分数列

https://www.ybtoj.com.cn/contest/129/problem/5#submit_code

dp(i)表示到第i个数的划分数、

再开两个数组，last_max[],last_min[],表示以i结尾的最长不上升/下降的序列起点前一位

即，用a{last_min[i-1]-1}~a{i-1}可以表示i尾最长的单调不降字串,max同理

整个递推分两步：

1.比较a[i]与[i-1]，大于：更新max  小于：更新min

另一个自动改为i单个字串就，更新为i-1.

2.更新dp(i):dp(i) = min{last_max[i],last_min[i]}+1

求f函数

https://www.ybtoj.com.cn/contest/129/problem/6

只需考虑1-100的特殊情况即可。

第一步要把x换成x+11,范围为11~111.

第二步进函数，101~111的部分直接-10,其他部分继续递推。

可见，进-10操作之前，每个数要+11操作k次以超过100，并进行k次-10.

从100-1倒着递推即可。

无限序列

https://www.ybtoj.com.cn/contest/129/problem/7

先列出前几种变化：

F1 = 1；

F2 = 101；

F3 = 10110；

F4 = 10110101；

F5 = 1011010110110；

推出Fi = Fi-1+Fi-2这里指的不是相加，而是序列首尾相接

序列首尾相接怎么实现呢？只需要用数组num1i表示第i个序列1的个数，

在进行结合时将size（大小）和num均相加作为记录即可。

关于回答：[a,b]区间的1个数等价于[1,b]区间和[1,a-1]区间num差值

序列个数

https://www.ybtoj.com.cn/contest/129/problem/8

由这个题能想到矩阵

也就是题中所谓

b[1]~b[i]中≤i的数的个数

创建矩阵的依据：

横坐标表示第i个数，纵坐标表示数i位置

得到01矩阵（以53421为例）

00001

00010

01000

00100

10000

重点来了：a[i]表示以i,i围成的正方形中1个数，a[i]-a[i-1]就是两个矩形差L形中1的个数

我们可以从a[1]开始填数，确定方案数。

显然，每行每列最多只有1个1，则L形的情况有3种，设c = a[i]-a[i-1];

1.c==0,次层不填1；

2.c==1，L形填入1个1，L形总共有i+i-1个位置,前面填了a[i-1]个位置，每个使L形可选位置减少两个（想想为什么）,则可填1的位置有i+i-1-a[i-1]*2

3.c==2,L形必须在横竖各填1个1，各有i-1个位置；前面填了a[i-1]个位置,使横竖可选位置各减少一个，排列组合一下，(i-1-a[i-1])^2

4.c>=3，不可能填的下，方案数为0.

将每层方案数相乘，即可得到答案

贪心算法

1.奶牛晒衣服

https://www.ybtoj.com.cn/contest/130/problem/1

这题的贪心策略很明确，每次烘干湿度最大的，这样就使湿度最大的尽可能小，整体减少就会更快

2.雷达装置

https://www.ybtoj.com.cn/contest/130/problem/2

解决思路很有意思：

对于每个建筑物，都会有一个固定的雷达建造区间来辐射到它（若区间为0，则输出-1）

没错，就是点（x,y）半径为d的圆与x轴交点。

那么我们就要每次让雷达建造在区间里，并保证这个雷达能尽可能“顺便”在其他区间里，减少建造次数。

考虑按x坐标左——右循环，每次让雷达尽可能造在最右边，即贪心最优方案。

3.畜栏预定

https://www.ybtoj.com.cn/contest/130/problem/3

关于畜栏预定，证明要安排的最后一头牛，找到适配的任意畜栏（即，当前牛开始时间晚于畜栏中最后一牛结束时间），若找不到，畜栏++.

用优先队列维护一个结构体，拥护两个变量（r,id）表示序号为id畜栏的--结束时间，按结束时间排序。

4.荷马史诗