【每周算法】第十二周：线性DP

· 2025-11-29 · # 每周算法 # 学习笔记 # 编程

笔记

dp是一种时间换空间的算法，可以先把记忆化 dfs写出来，改成 dp；或写出 dfs，将参数写成 dp的状态

Luogu P1115 最大子段和

这还是一个比较简单的题

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+10;
int a[N],f[N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d",&a[i]);
	}
	int ans = INT_MIN;
	for(int i= 1;i <= n;i++){
		// 要么从前一个转移，要么新开一个子段
		f[i] = max(f[i-1]+a[i],a[i]);
		ans = max(ans,f[i]);
	}
	printf("%d",ans);
	return 0;
}

Luogu P3842 [TJOI2007] 线段

这题也是看了这篇题解才写出来的

有些绕,我也讲不清楚,还是看那篇题解吧(对着deepsee调了一个小时的bug,死活看不出来为什么错了,然后手玩样例才明白)

#include<bits/stdc++.h>

using namespace std;

const int N = 2e4+10;
int l[N],r[N],f[N][5];

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&l[i],&r[i]);
	}
	f[1][0] = r[1]-1+r[1]-l[1];
	f[1][1] = r[1]-1;
	for(int i = 2;i <= n;i++){
		f[i][0] = min(f[i-1][0]+abs(l[i-1]-r[i])+r[i]-l[i]+1,f[i-1][1]+abs(r[i-1]-r[i])+r[i]-l[i]+1);
		f[i][1] = min(f[i-1][0]+abs(l[i-1]-l[i])+r[i]-l[i]+1,f[i-1][1]+abs(r[i-1]-l[i])+r[i]-l[i]+1);
	}
	int ans = min(f[n][0]+abs(n-l[n]),f[n][1]+abs(n-r[n]));
	printf("%d",ans);
	return 0;
}

Luogu P2758 编辑距离

$f_{i,j}$ 表示 $a$ 串前 $i$ 个转移至 $b$ 串前 $j$ 个至少需要多少次操作

其他没啥好说的了,直接说转移方程了

就是有3种不同的状态可以转移:

两个字符串同时添加一个字符,此时如果这个字符不同则修改,否则不动
$b$ 串加一个字符,此时 $a$ 串就需要额外加一个字符
$a$ 串加一个字符,同理, $b$ 串也需要额外加一个字符

#include<bits/stdc++.h>

using namespace std;

const int N = 2010;
char a[N],b[N];
int f[N][N];

int main(){
	scanf("%s%s",a,b);
	int n = strlen(a),m = strlen(b);
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= m;j++){
			if(i == 0){
				f[i][j] = j;
			} else if(j == 0){
				f[i][j] = i;
			} else{
				f[i][j] = min({f[i-1][j-1]+(a[i-1]!=b[j-1]),f[i-1][j]+1,f[i][j-1]+1});
			}
		}
	}
	printf("%d",f[n][m]);
	return 0;
}

Luogu P1140 相似基因

呵呵,说出来你可能不信,我看不懂题目

Luogu P1006 [NOIP 2008 提高组] 传纸条

我记得我以前写过一个这样的题解:【题解】洛谷P1006 [NOIP 2008 提高组] 传纸条,这里就不细说了

#include<bits/stdc++.h>

using namespace std;

const int N = 60;
int a[N][N],dp[N][N][N][N];

int main(){
	int m,n;
	cin >> m >> n;
	for(int i = 1;i <= m;i++){
		for(int j = 1;j <= n;j++){
			cin >> a[i][j];
		}
	}
	for(int i = 1;i <= m;i++){
		for(int j = 1;j <= n;j++){
			for(int k = i+1;k <= m;k++){
				for(int l = 1;l < j;l++){
					dp[i][j][k][l] = max({dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]})+a[i][j]+a[k][l];
				}
			}
		}
	}
	cout << dp[m-1][n][m][n-1];
	return 0;
}

David 100628 或 Luogu T386257 【模板】最长公共子序列

额,虽然我学了部分提高内容,但我似乎无法做出来,不过我呢看过一篇笔记使用二分法作的 LIS（最长上升子序列),这题应该也是二分

先放dp版（由于空间内存限制，无法将数组开到1e5，就只能开到2000了，当然如果用滚动数组也可以，反正都会TLE，不如轻快一点)

// 50pts, RE
#include<bits/stdc++.h>

using namespace std;

const int N = 2010;
int a[N],b[N],f[N][N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d",&a[i]);
	}
	for(int i = 1;i <= n;i++){
		scanf("%d",&b[i]);
	}
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= n;j++){
			if(i == 0){
				f[i][j] = 0;
			} else if(j == 0){
				f[i][j] = 0;
			} else{
				f[i][j] = max({f[i][j-1],f[i-1][j],f[i-1][j-1]+(a[i]==b[j])});
			}
		}
	}
	printf("%d",f[n][n]);
	return 0;
}

好的，我也是问了一下deepseek，发现只需要将原问题转换为 LIS问题即可

（以下是 LIS二分的解，来自ZQ教练的模考讲评)

0725 模考讲评

#include<bits/stdc++.h>
#define iter vector<int>::iterator

using namespace std;

const int N = 1e5+10;
int a[N],b[N],mp[N];
int LIS(vector<int>v){
	vector<int>d;
	for(int g:v){
		iter it = lower_bound(d.begin(),d.end(),g);
		if(it == d.end()){
			d.push_back(g);
		} else{
			*it = g;
		}
	}
	return d.size();
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d",&a[i]);
		mp[a[i]] = i;
	}
	vector<int>v;
	for(int i = 1;i <= n;i++){
		int x;
		scanf("%d",&x);
		v.push_back(mp[x]);
	}
	printf("%d",LIS(v));
	return 0;
}

这种用下标做的为什么是对的呢？

我们取出来的是两个完全相同的集合（下标在 $b$ 中的与值在 $a$ 中的)，这一点很好理解
因为我们是在索引中去子序列，所以其下标在 $b$ 数列中一定为子序列
因为我们取的是上升子序列，所以取得的值（即 $a$ 数列中的下标)在 $a$ 数列中一定为子序列
因为我们取的是最长的，所以我们的子序列一定最长