自动搬运

查看原文

来自洛谷，原作者为

	Zilljy258 太沙雕了，，，

搬运于2025-08-24 22:17:37，当前版本为作者最后更新于2022-07-04 13:58:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我向来是遇到动规就懵逼的那种人......

题目传送门

---

大体思路：

拿到一道动态规划题目怎么办？

坦然逝去。

当然是去推状态转移方程啦！

怎么推？

如果你不愿意看，可以直接去看状态转移方程。

一般我会用一个名为 $f$ 的数组去推导（我想这也是大多数人的嗜好）。

我们把 $f_{i,j}$ 设为取序列 $a$ 的前 $i$ 项，序列 $b$ 的前 $j$ 项的最长公共子序列（ $LCS$ ），那么状态转移方程就是：

$$f_{i,j}=\begin{cases}\max(f_{i-1,j},f_{i,j-1})\\f_{i-1,j-1}+1(|a-b| \leq 4) \end{cases} $$

当然，你也可以设为设为取序列 $a$ 的第 $i$ 项，序列 $b$ 的第 $j$ 项的最长公共子序列。但是这样做不但状态转移方程变了，而且似乎还要把 $f$ 数组初始化......

这里提一句，其实推导状态转移方程有技巧的。这里有我总结出来的两种方法：

1. 手打样例，亲手去模拟一下样例，可以发现规律。

2. 根据题目描述。有些题目甚至直接把方程打了出来，就算不是这样我们也可以根据题目给出的蛛丝马迹进行推导。

3. 借鉴题解，参考题解。

---

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#define forr(a,b) for(int i=a;i<=b;i++) //简化一下
#define foor(a,b) for(int j=a;j<=b;j++)
using namespace std;
int a[1001]={0},b[1001]={0};
int f[1001][1001]={0};
int main(){
	int n;
	cin>>n;
	forr(1,n) cin>>a[i];
	forr(1,n) cin>>b[i];
	forr(1,n){
		foor(1,n){
			if(abs(a[i]-b[j])<=4){ //abs取绝对值
				f[i][j]=max(f[i][j],f[i-1][j-1]+1);
			}
			else{
				f[i][j]=max(f[i-1][j],f[i][j-1]);
			}
		}
	}
	cout<<f[n][n]<<endl;
	return 0;
}

---

总结：

注意推导状态转移方程的部分。

后记：

大佬们都说这题很简单，不过我觉得对我来说还挺难的。

动态规划我学的一直都不太好，这道题目做的时候我也是参考了题解，希望这篇题解没有错误，但愿能过吧。