1. Toy模板网首页
  2. > Toy博客

《算法竞赛进阶指南》0x51 线性DP

9月前 作者：hydqiln 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了《算法竞赛进阶指南》0x51 线性DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

0x51 线性DP

271. 杨老师的照相排列

题意：

N N N 个人站成左端对齐的 k k k 排，每排有 N i N_i Ni​ 人， N i > N j N_i > N_j Ni​>Nj​ 如果 i < j i < j i<j，则 N i > N j N_i > N_j Ni​>Nj​ 。每一排从左到右身高递减，每一列从后到前身高递减。询问方案数。

解析：

按照身高从大到小的顺序决定位置。在任意时刻，已经确定位置的人在每一行中一定是从左开始的连续位置。

用 k k k 元组可以描述当前已经确定的位置。在决定当前人的位置时，可放的排为没放满的排，且放完后满足 n i > n j ( i < j ) n_i > n_j (i < j) ni​>nj​(i<j)， n i n_i ni​ 为第 i i i 排已经放的人数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 32;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n[6];
int k; 
ll dp[maxn][maxn][maxn][maxn][maxn];
int check(int a, int b, int c, int d, int e){
	return a >= b && b >= c && c >= d && d >= e && e >= 0;
}
void solve(){
	memset(dp, 0, sizeof(dp));
	dp[0][0][0][0][0] = 1;
	for(int a = 0; a <= n[1]; a++){
		for(int b = 0; b <= n[2]; b++){
			for(int c = 0; c <= n[3]; c++){
				for(int d = 0; d <= n[4]; d++){
					for(int e = 0; e <= n[5]; e++){
						if(!check(a, b, c, d, e))
							continue;
						if(check(a-1, b, c, d, e))
							dp[a][b][c][d][e] += dp[a-1][b][c][d][e];
						if(check(a, b-1, c, d, e))
							dp[a][b][c][d][e] += dp[a][b-1][c][d][e];
						if(check(a, b, c-1, d, e))
							dp[a][b][c][d][e] += dp[a][b][c-1][d][e];
						if(check(a, b, c, d-1, e))
							dp[a][b][c][d][e] += dp[a][b][c][d-1][e];
						if(check(a, b, c, d, e-1))
							dp[a][b][c][d][e] += dp[a][b][c][d][e-1];
					}
				}
			}
		}
	}
	//cout << "ans = ";
	cout << dp[n[1]][n[2]][n[3]][n[4]][n[5]] << endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	while(1){
		cin >> k;
		if(k == 0)
			break;
		memset(n, 0, sizeof(n));
		for(int i = 1; i <= k; i++)
			cin >> n[i];
		solve();
	}
	return 0;
}

最长公共上升子序列

题意：

给定两个序列 a , b a, b a,b，询问最长公共上升子序列的长度

解析：

令 f i , j f_{i,j} fi,j​ 为在 a a a 的前 i i i 个数和 b b b 的前 j j j 个数中以 b j b_j bj​ 的最长公共上升子序列的长度。

  • 不选 a i a_i ai​， f i , j = f i − 1 , j f_{i,j} = f_{i-1, j} fi,j​=fi−1,j​
  • 选了 a i a_i ai​， f i , j = max ⁡ b k < b j { f i − 1 , k + 1 } f_{i,j} = \max\limits_{b_k<b_j}\{f_{i-1,k}+1\} fi,j​=bk​<bj​max​{fi−1,k​+1}

此时时间复杂度为 O ( n 3 ) O(n^3) O(n3)。

容易发现每次都是从 a i > b k a_i > b_k ai​>bk​ 的前缀最大值转移过来，增加一个变量记录 f i − 1 , k f_{i-1,k} fi−1,k​ 的前缀最大值。此时时间复杂度为 O ( n 2 ) O(n^2) O(n2)

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n, a[maxn], b[maxn];
int f[maxn][maxn], ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++)
		cin >> b[i];
	for(int i = 1; i <= n; i++){
		int maxx = 0;
		for(int j = 1; j <= n; j++){
			f[i][j] = f[i-1][j];
			if(a[i] == b[j])
				f[i][j] = max(f[i][j], maxx+1);
			else if(a[i] > b[j])
				maxx = max(maxx, f[i][j]);
			if(i == n)
				ans = max(ans, f[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}

分级

题意：

给定序列 A A A，构造非严格的单调序列 B B B，使 S = ∑ i = 1 n ∣ A i − B i ∣ S = \sum\limits_{i=1}\limits^n |A_i-B_i| S=i=1∑n​∣Ai​−Bi​∣ 最小。询问最小值。

解析

结论： 一定存在一组最优解，使得每个 B i B_i Bi​ 都存在 j j j，满足 B i = A j B_i = A_j Bi​=Aj​

令 f i , j f_{i,j} fi,j​ 为确定前 i i i 数，且第 i i i 个数为 C j C_j Cj​ ， C C C 为升序排序后的 A A A 序列。
f i , j = min ⁡ k < = j { f i − 1 , k + ∣ C j − A i ∣ } f_{i,j} = \min\limits_{k <= j}\{ f_{i-1,k} + |C_j-A_i|\} fi,j​=k<=jmin​{fi−1,k​+∣Cj​−Ai​∣}维护前缀最小值，可在 O ( 1 ) O(1) O(1) 时间转移

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 2e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n, a[maxn], c[maxn];
int ans = INF;
bool cmp(int a, int b){
	return a > b;
}
int f[maxn][maxn];
void solve(){
	memset(f, 0, sizeof(f));
	int res = INF;	
	for(int i = 1; i <= n; i++){
		int minn = INF;
		for(int j = 1; j <= n; j++){
			minn = min(minn, f[i-1][j]);
			f[i][j] = minn + abs(a[i]-c[j]);
		}
	}
	for(int i = 1; i <= n; i++)
		res = min(res, f[n][i]);
	ans = min(ans, res);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		c[i] = a[i];
	}
	sort(c+1, c+1+n);
	solve();
	
	sort(c+1, c+1+n, cmp);
	solve();
	
	cout << ans << endl;
	return 0;
}

移动服务

题意：

有 3 个人。有 n n n 个请求一个人去某地，移动有代价。依次满足请求，询问最小代价。

题意：

令 f i , x , y f_{i, x, y} fi,x,y​ 表示满足前 i i i 个请求后，三人位于 p o s i , x , y pos_i, x, y posi​,x,y 时的最小代价。

每个状态可以转移到另外三个状态，见代码。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int L, n;
int p[maxn], c[210][210];
int dp[maxn][210][210];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> L >> n;	
	for(int i = 1; i <= L; i++)
		for(int j = 1; j <= L; j++)
			cin >> c[i][j];
	for(int i = 1; i <= n; i++)
		cin >> p[i];
	
	memset(dp, INF, sizeof(dp));
	dp[0][1][2] = 0; p[0] = 3;
	for(int i = 0; i < n; i++){
		for(int x = 1; x <= L; x++){
			for(int y = 1; y <= L; y++){
				if(x == y || y == p[i] || x == p[i])
					continue;
				int u = p[i+1];
				dp[i+1][x][y] = min(dp[i+1][x][y], dp[i][x][y] + c[p[i]][u]);
				dp[i+1][x][p[i]] = min(dp[i+1][x][p[i]], dp[i][x][y] + c[y][u]);
				dp[i+1][p[i]][y] = min(dp[i+1][p[i]][y], dp[i][x][y] + c[x][u]);
			}
		}
	}
	int res = INF;
	for(int i = 1; i <= L; i++)
		for(int j = 1; j <= L; j++)
			res = min(res, dp[n][i][j]);
	cout << res << endl;
	return 0;
}

传纸条

题意：

m × n m\times n m×n 的矩阵，每次可以向右或者向下走一步。从左上角都右下角选择两条互不相交（在路径端点可以相交）的路径，使点权和最大。

解析：

令 f i , j , x , y f_{i,j,x,y} fi,j,x,y​ 为第一条路径走到 ( i , j ) (i,j) (i,j) 且第二条路径走到 ( x , y ) (x,y) (x,y) 的最大点权和

对于 ( i , j ) = ( x , y ) (i,j) = (x,y) (i,j)=(x,y) 的状态，只计算一次点权

也可以网络流。

把每个点拆成入点和出点，入点向出点连边，容量1，费用为点权。

每个点的出点向能到达的点的入点连边，容量INF，费用 0；再连一条边，容量INF，费用 0.

源点向起点的入点连边，容量2，费用 0；终点的出点向汇点连边，容量2，费用 0 。

参考洛谷上 Duan2baka 大佬题解

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int dp[55][55][55][55],a[55][55],n,m;
int main(){
	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 = 1; k <= m; k++)
                for (int l = 1; l <= n; l++) {
                	dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];
                	if(i==k && j==l) dp[i][j][k][l] -= a[i][j];
                }
    cout << dp[m][n][m][n];
}

饼干

题意：

m m m 个饼干，分给 n n n 个人。每个人有参数 g i g_i gi​，如果有 a i a_i ai​ 个人的饼干多于 i i i ，则 i i i 产生 a i × g i a_i \times g_i ai​×gi​ 的怨气。

每个孩子最少分一个饼干，询问最少的怨气。

解析：

贪心的考虑， g g g 大的人一定分的多于 g g g 少的人。否则可以交换，结果不会变劣。

令 f i , j f_{i,j} fi,j​ 为前 i i i 个孩子分了 j j j 个饼干的最小怨气和。

如果当前第 i i i 个人的饼干数大于 1，则前 i i i 个人饼干数都大于 1。每个人都减去一个饼干， a a a 不变，所以 f i , j = f i , j − i f_{i,j} = f_{i,j-i} fi,j​=fi,j−i​ 。

如果当前第 i i i 个人的饼干数为1，枚举有多少人饼干数不为 1

f i , j = min ⁡ 0 ≤ k < i { f k , j − i + k + k ∑ t = k + 1 i g t } f_{i,j} = \min\limits_{0\le k<i}\{f_{k,j-i+k}+k\sum\limits_{t = k+1}\limits^ig_t\} fi,j​=0≤k<imin​{fk,j−i+k​+kt=k+1∑i​gt​}

时间复杂度为 O ( n 3 m ) O(n^3m) O(n3m)。也可以前缀和优化一下，时间复杂度变成 O ( n 2 m ) O(n^2m) O(n2m)。文章来源地址https://www.toymoban.com/news/detail-422943.html

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define mkp(a, b) make_pair((a), (b))
const int maxn = 3e2+10;
const int maxm = 5e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

struct node{
	int g, id;
	node(){}
	node(int g, int id) : g(g), id(id){}
	bool operator < (const node &b) const{
		return g > b.g;
	}
}s[maxn];
int g[maxn], sum[maxn];
int f[maxn][maxm];
pii fr[maxn][maxm];
int res[maxn];
void cal(int x, int y){
	if(x == 0)
		return;
	cal(fr[x][y].first, fr[x][y].second);
	if(fr[x][y].first == x){
		for(int i = 1; i <= x; i++)
			res[s[i].id]++;
	}
	else{
		for(int i = fr[x][y].first+1; i <= x; i++)
			res[s[i].id] = 1;
	}
}
int n, m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> s[i].g;
		s[i].id = i;
	}		
	sort(s+1, s+1+n);
	for(int i = 1; i <= n; i++)
		sum[i] = sum[i-1] + s[i].g;
	memset(f, INF, sizeof(f));
	f[0][0] = 0;
	
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= m; j++){
			f[i][j] = f[i][j-i];
			fr[i][j] = mkp(i, j-i);
			for(int k = 0; k < i; k++){
				if(f[i][j] > f[k][j-i+k] + k*(sum[i]-sum[k])){
					f[i][j] = f[k][j-i+k] + k*(sum[i]-sum[k]);
					fr[i][j] = mkp(k, j-i+k);
				}
				
			}
		}
	}
	cout << f[n][m] << endl;
	cal(n, m);
	for(int i = 1; i <= n; i++)
		cout << res[i] << " ";
	cout << endl;
	return 0;
}

到了这里，关于《算法竞赛进阶指南》0x51 线性DP的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 《算法竞赛进阶指南》------图论篇

    《算法竞赛进阶指南》------图论篇

    Telephone Lines 题意：从1到N修一条电缆，有p对电线杆之间是可以连接的，电信公司可以提供k条电缆，其他的由John提供，求john提供的电缆的最长的那根的长度（ret）。 思路：实则是求最短最长的边。 二分结果(sum)。对于 边值sum, 电信公司需要提供电缆。 用djk 计算 1-n 路径上的

    2024年02月03日
    浏览(35)

  • 算法专题：线性DP

    参考练习习题总集 第一道题就是困难题让我很难蚌，真是磨人啊。 嗨嗨嗨，思想差不多的，又水一道困难题。 记忆化搜索。这里的记忆化搜索本质就是线性DP。做这道题时真是气死我了，一开始明明记着长度为0的时候需要特判，但是后面做着做着就忘了加上去，交了一次又

    2024年02月19日
    浏览(37)
  • 算法竞赛备赛之动态规划训练提升，DP基础掌握

    算法竞赛备赛之动态规划训练提升，DP基础掌握

    01背包问题是在M件物品中选择若干件放在空间为W的背包中，每件物品的体积为W1，W2至Wn，价值为P1，P2至Pn，01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。 01背包问题常常采用动态规划的方法去求解，状态转移方程为：F(W,i)=max{F(W,

    2024年02月08日
    浏览(41)

  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP：状态转移表达式存在明显的线性关系。 区间DP：与顺序有关，状态与区间有关。 题目1 ：数字三角形。 解题思路：直接DP即可， f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ，注意 f[i-1][j] 不存在的情况（最后一个点）和 f[i-1][j-1] 不存在的情况（第一个点）。

    2024年02月04日
    浏览(49)
  • Peter算法小课堂—线性dp

    Peter算法小课堂—线性dp

    今天，你读完这篇文章，普及组的动态规划已经可以秒了。 求两个数列的最长公共子序列（Longest Common Subsequence，LCS）的长度。 数列 X 和 Y 的最长公共子序列 Z，是指 Z 既是 X 的子序列，又是 Y 的子序列，而且任意长度超过 Z 的数列 Z∗ 都不符合这个性质。 f[i][j]表示

    2024年04月23日
    浏览(36)
  • C++动态规划-线性dp算法

    C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路： 代码测试：  三步问题 思路： 代码测试： 最小花费爬楼梯 思路： 代码测试：  路径问题 数字三

    2024年02月19日
    浏览(46)
  • AcWing算法学习笔记：动态规划（背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索）

    AcWing算法学习笔记：动态规划（背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索）

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历，当更新f[i, j]时，f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历，当更新f[i, j]时，f[i - 1,

    2024年02月21日
    浏览(42)
  • 算法基础复盘笔记Day10【动态规划】—— 线性DP

    算法基础复盘笔记Day10【动态规划】—— 线性DP

    ❤ 作者主页：欢迎来到我的技术博客😎 ❀ 个人介绍：大家好，本人热衷于 Java后端开发 ，欢迎来交流学习哦！(￣▽￣)~* 🍊 如果文章对您有帮助，记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉 1. 题目

    2023年04月21日
    浏览(79)
  • 猿创征文 |【算法面试入门必刷】动态规划-线性dp（一）

    猿创征文 |【算法面试入门必刷】动态规划-线性dp（一）

    📦个人主页：一二三o-0-O的博客 🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑） 👨‍💻作者简介：数据结构算法与音视频领域创作者 📒 系列专栏：牛客网面试必刷 📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，收获心仪Offer 📝推荐一个找工作

    2024年02月03日
    浏览(65)
  • 猿创征文 |【算法面试入门必刷】动态规划-线性dp（四）

    猿创征文 |【算法面试入门必刷】动态规划-线性dp（四）

    📦个人主页：一二三o-0-O的博客 🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑） 👨‍💻作者简介：数据结构算法与音视频领域创作者 📒 系列专栏：牛客网面试必刷 📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，收获心仪Offer 📝推荐一个找工作

    2024年02月02日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包