YBTOJ 递推算法合集

栈的问题

栈只有两种操作：push和pop。

设 $f[i][j]$ 为当前有 $i$ 个数未输出，$j$ 个数没入过栈的方案数，可以得到：

• push操作： $f[i][j-1]$
• pop操作： $f[i-1][j]$

故 $f[i][j]=f[i-1][j]+f[i][j-1]$，初始化 $f[i][0]=1$（没有数可以入栈，那么只能不断出栈），$f[n][n]$ 即为答案。

划分数列

设 $f[i][0]$ 为以 $a[i]$ 结尾，当前数列单调不升的方案数，$f[i][1]$ 为以 $a[i]$ 结尾，当前数列单调不减的方案数，则：

• 当 $a[i]>=a[i-1]$，那么构成单调不降序列可以自己新开，也可以与上一个数合并，即 $f[i][1]=min(f[i-1][1],f[i-1][0]+1)$，否则构成单调不降序列只能自己新开，即 $f[i][1]=min(f[i-1][0],f[i-1][1])+1$
• 当 $a[i]<=a[i-1]$，同理可得 $f[i][0]=min(f[i-1][0],f[i-1][1]+1)$，否则 $f[i][0]=min(f[i-1][0],f[i-1][1])+1$

求f函数

按给的公式暴力记搜

无限序列

做的时候降智了没推几组就以为是两个10110两个11010交替，光荣爆零

继续手推发现，若记第 $i$ 次操作后得到的序列为 $s[i]$，那么有 $s[i]=s[i-1]+s[i-2]$，令 $siz[i]$ 为第 $i$ 次操作后得到的序列长度，$num[i]$ 为第i次操作后得到的序列中1的个数，就可以利用前缀和思想得到答案。

code：

#include
#define int long long
#define ff(i,s,e) for(int i(s);i<=(e);++i)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=92;
int q,a,b;
int siz[N],num[N];
inline int qwq(int x){
    ff(i,0,90){
        if(siz[i]==x) return num[i];
        else if(siz[i]>x) return num[i-1]+qwq(x-siz[i-1]);
		//找到第一个长度小于x的序列，由于序列是递推重复的，那么siz[i-1]+1~x的对答案贡献
		//和1~x-siz[i-1]的贡献是一样的，可以递归求解 
    }
    return 0;
}
signed main(){
    q=read();
    siz[1]=1,siz[2]=2,num[1]=num[2]=1;
    ff(i,3,90) siz[i]=siz[i-1]+siz[i-2],num[i]=num[i-1]+num[i-2];
    while(q--){
        a=read(),b=read();
        printf("%lld\n",qwq(b)-qwq(a-1));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

序列个数

神仙题

考虑将每个序列 $b$ 都用矩阵表示，例如 $1,5,3,4,2$ 可表示为：

1 0 0 0 0

0 0 0 0 1

0 0 1 0 0

0 0 0 1 0

0 1 0 0 0

那么发现每个 $a[i]$ 在矩阵中的意义变为：$(1,1)$ 到 $(i,i)$ 构成的方阵里有多少个1（这是怎么想到的qwq

由于矩阵的每行每列都有且只有一个1，就可以进行分类讨论：

• $a[i]<a[i-1]$，显然无解
• $a[i]=a[i-1]$，啥也不干
• $a[i]=a[i-1]+1$，有 $i\ast 2-1$ 个位置可填，之前的矩阵里已经填了 $a[i-1]$ 个 $a$，占据了 $a[i-1]$ 行和 $a[i-1]$ 列，不能再填，则 $ans\ast =(i\ast 2-1-2\ast a[i-1])$
• $a[i]=a[i-1]+2$，则一个1填在新增的一行里，一个1填在新增的一列里，$(i,i)$不可填，各有 $(i-1-a[i-1])$ 种方案，$ans\ast =(i-1-a[i-1]{)}^2$
• $a[i]>=a[i-1]+3$，显然无解

等距跳跃

看好题：“这种青蛙总是以直线跳过稻田”说明直线一定都得贯穿地图！！！

由于两点确定一条直线，看到数据范围发现可以枚举每一对点，则当前直线斜率与直线上点间距均变为已知，将点按横纵坐标升序排序来保证在结点 $i$ 之前枚举的结点 $j$ 们全部在 $i$ 的左或上方，就可以用 $i$ 关于 $j$ 的对称点 $k$ 来进行递推：

若 $k$ 超出地图范围，说明 $j->i$ 可以作为一条路径的起点，$f[i][j]=2$

若 $k$ 位置正好存在某个结点，则 $\dots ->k->j->i$ 可作为一条路径，$f[i][j]=f[j][k]+1$，由于之前排序过，而 $j$ 在 $i$ 的左或上方，$k$ 也一定在 $i$ 的左或上方，所以 $f[j][k]$ 一定被更新过，可以放心递推。

否则当前路径不合法，$f[i][j]=-inf$

递推完成，可是还有一个问题：当前只保证了路径向左或向上穿过地图，向右或向下呢？

这个问题也不难解决，只需在统计答案时计算 $j$ 关于 $i$ 的对称点 $k$，只有 $k$ 越界的时候才更新答案即可。

code：

#include 
#define ll long long
#define ff(i,s,e) for(int i(s);i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=5005,M=3005;
int n,r,c;
struct qwq{
	int x,y;
}a[N];
int f[N][N],s[N][N];
inline bool cmp(qwq a,qwq b){
	if(a.y!=b.y) return a.y<b.y;
	return a.x<b.x;
}
inline qwq get(qwq a,qwq b){
	return qwq{(a.x<<1)-b.x,(a.y<<1)-b.y};
}
signed main(){
	r=read(),c=read();
	n=read();
	ff(i,1,n) a[i].x=read(),a[i].y=read();
	sort(a+1,a+n+1,cmp);
	ff(i,1,n) s[a[i].x][a[i].y]=i;
	int ans=0;
	ff(i,2,n){
		ff(j,1,i-1){
			qwq k=get(a[j],a[i]);
			if(k.x<1||k.x>r||k.y<1||k.y>c) f[i][j]=2;
			else if(s[k.x][k.y]) f[i][j]=f[j][s[k.x][k.y]]+1;
			else f[i][j]=-1e9;
		}
	}
	ff(i,2,n){
		ff(j,1,i-1){
			qwq k=get(a[i],a[j]);
			if((k.x<1||k.x>r||k.y<1||k.y>c)&&f[i][j]>=3) ans=max(ans,f[i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48