《算法竞赛入门到进阶》——动态规划

2023-12-13 22:28:01

7.1 基础DP（P116）

这部分主要涉及背包问题、最长公共子序列、最长递增子序列等问题。由于这些经典问题在之前的学习中已经涉及，所以不在此赘述。

例1 P1356 数列的整除性

问题描述

给定一个数组 a[] ，数组中元素的正负号可以任意指定，问该数组所有可能的元素和中，是否在某个和能被 $k$ 整除。

思路

定义状态 dp[i][j] 表示：已经指定了前 i 个数的正负号的情况下，这些数的和能够模 k 余 j 。显然，状态 dp[n][0] 即为最终答案。状态转移方程比较常规，见代码。

代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4+5;
const int maxk = 1e2+5;

int M;
int n, k;
bool dp[maxn][maxk];
int a[maxn];

int main(){
	cin>>M;
	while(M--){
		memset(dp, 0, sizeof(dp));
		memset(a, 0, sizeof(a));
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			a[i] = (abs(a[i]))%k;
		}
		dp[0][0] = 1;
		for(int i=1;i<=n;i++){
			for(int j=0;j<k;j++){
				dp[i][j] = dp[i-1][(j-a[i]+k)%k] || dp[i-1][(j+a[i]+k)%k];
			}
		}
		if(dp[n][0]) cout<<"Divisible";
		else cout<<"Not divisible";
		cout<<'\n';
	}
}

例2 POJ 1239 Increasing Sequences

题目大意

给定一个由数字构成的字符串 s ，问怎样添加逗号才能使之成为一个严格递增的序列，返回所有合法序列中最后一个数最小，且第一个数尽可能大的序列（如果第一个数字相等则比较第二个数字，以此类推）。

如 2315 对应的答案为：2,3,15 。

思路

两次dp。第一次dp对应状态 dp1[] ，dp1[i] 表示：仅考虑前 i 个字符，能保证序列严格递增的以 i 为结尾的数字的最小长度。显然，题目中要求的“最后一个数最小”对应了状态 dp1[s.size()-1] 。第二次dp对应状态 dp2[] ，dp2[i] 表示：仅考虑后 i 个字符，保证序列严格递增的以 i 为开始的数字的最大长度。显然，题目中要求的“第一个数尽可能大”对应了状态 dp2[0]。

代码

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

const int maxn = 100;

string s;
int dp1[maxn], dp2[maxn];

int myStoi(string s){
	int res = 0;
	for(int i=0;i<s.size();i++){
		res *= 10;
		res += s[i]-'0';
	}
	return res;
}

bool check(int s1, int l1, int s2, int l2){
	int newL1 = l1, newL2 = l2;
	int cnt1 = 0, cnt2 = 0;
	for(int i=0;i<l1;i++){
		if(s[s1+i]=='0'){
			newL1--;
			cnt1++;
		}
		else break;
	}
	for(int i=0;i<l2;i++){
		if(s[s2+i]=='0'){
			newL2--;
			cnt2++;
		}
		else break;
	}
	if(newL1 > newL2) return true;
	else if(newL2 > newL1) return false;
	else{
		for(int i=cnt1, j=cnt2;i<l1&&j<l2;i++, j++){
			if(s[s1+i]>s[s2+j]) return true;
			else if (s[s1+i]<s[s2+j]) return false;
		}
		return false;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	while(1){
		cin>>s;
		if(s == "0") break;
		dp1[0] = 1;
		for(int i=1;i<s.size();i++){
			dp1[i] = i+1;
			for(int j=1;j<=i;j++){
				int s1 = i-j+1, l1 = j;
				int s2 = s1-dp1[i-j], l2 = dp1[i-j];
				if(check(s1, l1, s2, l2)){
					dp1[i] = j;
					break;
				}
			}
		}
		int final = s.size()-dp1[s.size()-1];
		dp2[final] = dp1[s.size()-1];
		for(int i=final-1;i>=0;i--){
			if(s[i]=='0'){
				dp2[i] = dp2[i+1]+1;
				continue;
			}
			for(int j=final-i;j>=1;j--){
				int s1 = i, l1 = j;
				int s2 = s1+l1, l2 = dp2[s2];
				if(check(s2, l2, s1, l1)){
					dp2[i] = j;
					break;
				}
			}
		}
		cout<<s.substr(0, dp2[0]);
		for(int i=dp2[0];i<s.size();){
			cout<<","<<s.substr(i, dp2[i]);
			i += dp2[i];
		}
		cout<<'\n';
	}
	return 0;
}

例3 POJ 1080 Human Gene Functions

思路

在朴素的LCS问题中，有如下转移方程：

if(s1[i] == s2[j]){
	dp[i][j] = dp[i-1][j-1]+1;
}
else{
	dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}

dp[i][j] 表示：字符串 a[] 的前 i 个字符和字符串 b[] 的前 j 个字符的最长匹配。由状态转移方程可知，dp[i][j] 有三个来源：

dp[i-1][j-1]，在本题中代表用 a[i] 和 b[j] 进行匹配。
dp[i-1][j]，在本题中代表用 a[i] 和 '-' 进行匹配。
dp[i][j-1]，在本题中代表用 '-' 和 b[j] 进行匹配。

代码

#include<iostream>
#include<string>
#include<map>
using namespace std;

const int maxn = 105;

const int mtx[5][5] = {
	{5, -1, -2, -1, -3},
	{-1, 5, -3, -2, -4},
	{-2, -3, 5, -2, -2},
	{-1, -2, -2, 5, -1},
	{-3, -4, -2, -1, 0}
};

int dp[maxn][maxn];
int n, m;
char a[maxn], b[maxn];
int T;
map<char, int> mp;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	mp['A']=0, mp['C']=1, mp['G']=2, mp['T']=3, mp['-']=4;
	cin>>T;
	while(T--){
		cin>>n>>a+1>>m>>b+1;
		dp[0][0] = 0;
		for(int i=1;i<=n;i++){
			dp[0][i] = dp[0][i-1]+mtx[mp['-']][mp[b[i]]];
		}
		for(int i=1;i<=m;i++){
			dp[i][0] = dp[i-1][0]+mtx[mp[a[i]]][mp['-']];
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				dp[i][j] = dp[i-1][j-1]+mtx[mp[a[i]]][mp[b[j]]];
				dp[i][j] = max(dp[i][j], dp[i][j-1]+mtx[mp['-']][mp[b[j]]]);
				dp[i][j] = max(dp[i][j], dp[i-1][j]+mtx[mp[a[i]]][mp['-']]);
			}
		}
		cout<<dp[n][m]<<'\n';
	}
	return 0;
}

7.3 区间DP（P134）

例1 POJ 3280 Cheapest Palindrome

题目大意

给定一个由小写字母构成的字符串，可以在字符串中任意添加、删除原字符串中包含的字母，每个字母有自己的添加、删除代价。问：要使原字符串变成回文串，所花费的最小代价是多少？

思路

定义状态 dp[i][j] 表示：把区间 [i, j] 变为回文串所需的最小代价。状态转移方程为：

if(str[i]==str[j]){
	dp[i][j] = dp[i+1][j-1];
}
else{
	dp[i][j] = min(dp[i+1][j]+cost[str[i]-'a'], dp[i][j-1]+cost[str[j]-'a']);
}

需要说明的是，对于任何区间，从一端删掉一个字母和在另一端加上该字母是等价的，所以每个字母仅添加和删除中较小的花费即可。

代码

#include<iostream>
using namespace std;

const int maxm = 2e3+5;
const int maxn = 30;

int n, m;
char str[maxm];
int cost[maxn];
char c;
int a, b;
int dp[maxm][maxm];

int main(){
	cin>>n>>m;
	cin>>str+1;
	for(int i=1;i<=n;i++){
		cin>>c;
		cin>>a>>b;
		cost[c-'a'] = min(a, b);
	}
	for(int len=2;len<=m;len++){
		for(int i=1;i+len-1<=m;i++){
			int j = i+len-1;
			if(str[i]==str[j]){
				dp[i][j] = dp[i+1][j-1];
			}
			else{
				dp[i][j] = min(dp[i+1][j]+cost[str[i]-'a'], dp[i][j-1]+cost[str[j]-'a']);
			}
		}
	}
	cout<<dp[1][m];
	return 0;
}

例2 HDU 4283 You Are The One

题目大意

有 n 个人排队出场，可以对队头的队员进行两种操作：出场，耗时 1 秒；入栈，不耗时。每个队员都有一个值 D[i] ，队员的愤怒值为等待时间乘上 D[i]。问：怎样安排队员出场才能使总的愤怒值最低。

思路

区间dp，定义状态 dp[i][j] 表示：仅考虑区间 [i, j] 内的队员，让他们全部出场的最小愤怒值。

对每个区间 [i, j] ，我们枚举 i 号队员是第几个出场的。如果 i 号队员在 k 号队员之后出场，则区间 [i, j]的出场顺序为：

[i+1, k] 先出场，对应 dp[i+1][k] 。
i 出场，对应 D[i]*(k-i) 。
[k+1, j] 出场，此时前面已经耗时 k-i+1 秒，所以这部分对应 dp[k+1][j]+(k-i+1)*(sum[j]-sum[k]) 。

于是有状态转移方程：

dp[i][j] = min(dp[i][j], dp[i+1][k]+(k-i)*D[i]+dp[k+1][j]+(k-i+1)*(sum[j]-sum[k]));

例3 HDU 4623 Palindrome Subsequences

题目大意

给定一个字符串 s，问其中包含了多少回文子串（子串中的字符下标可以不连续）。

思路

定义 dp[i, j] 表示：区间 [i, j] 中包含的回文子串数。显然，dp[i][i] 为 1 ，dp[1][n] 为最终答案。

根据容斥原理，得到状态转移方程：

dp[i][j] = dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];

特别地，如果有 dp[i] == dp[j] ，则有：

dp[i][j] += dp[i+1][j-1]+1;

例4 HDU 2476 String Painter

题目大意

给定两个字符串 s1, s2 ，每次操作把任意区间的所有字符改成特定字符，问最少需要多少次操作才能把 s1 变成 s2 。

思路

先考虑一个简化的问题：最少需要多少次操作才能把一个空白串变成 s2 。（P4170 [CQOI2007]涂色）

定义 dp[i][j] 表示：仅考虑区间 [i, j] ，把空白串刷成 s2 所需的最少操作数。显然，dp[i][i] 为 1 ，dp[1][n] 为简化问题的答案。考虑状态转移方程，如果有 s2[i] == s2[j] ，则 dp[i][j] = min(dp[i+1][j], dp[i][j-1]) ；否则有 dp[i][j] = min(dp[i+1][j], dp[i][j-1])+1 。然后枚举区间内的断点，将区间分为 [i, k] 和 [k+1, j] ，此时有状态转移 dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]) 。

然后考虑原问题，定义 ans[i] 表示：仅考虑区间 [1, n] ，把 s1 刷成 s2 所需的最少操作数。当 s1[i] == s2[i] 时，有 ans[i] = ans[i-1] ；否则，枚举区间内的断点，将区间分为 [1, k] 和 [k+1, i] ，此时有状态转移 ans[i] = min(ans[i], ans[k]+dp[k+1][i]) 。

7.4 树形DP（P139）

例1 HDU 2196 “Computer”

题目大意

给定一颗树，求到每个结点的最大距离。

思路

对于任意一个结点 i ，距离其最远的点要么在其子树上，要么不在其子树上。所以我们可以为每个结点设计定义三个状态：

dp[i][0] ：子树上结点到 i 的最长距离。
dp[i][1] ：子树上结点到 i 的次长距离（可以与最长距离相同）。
dp[i][2] ：非子树结点到 i 的最长距离。

显然，对于结点 i ，到其的最大距离为 max(dp[i][0], dp[i][2]) 。解决本题的关键在于，如何求出每个结点的三个状态。

我们考虑进行两次 dfs 。第一次dfs求出每个结点的 dp[i][0] 和 dp[i][1] ，这部分比较简单。第二次 dfs 利用父结点求出每个子结点的 dp[i][2] ，代码如下：

void dfs2(int x, int fa){
	for(int i=head[x];i!=0;i=edge[i].next){
		int to = edge[i].to, v = edge[i].v;
		if(to == fa) continue;
		// 如果这个子结点在最长子树上
		if(dp[to][0]+v == dp[x][0]){
			dp[to][2] = max(dp[x][1], dp[x][2])+v;
		}
		else{
			dp[to][2] = max(dp[x][0], dp[x][2])+v;
		}
		dfs2(to, x);
	}
}

例2 POJ 2378 Tree Cutting

题目大意

给定一颗树，输出所有满足下述条件的结点编号：删除该结点后，每颗新树的大小均小于等于原树的一半。

思路

仿照重链剖分中求 siz[] 和 son[] 的方法，判断每个结点 siz[son[x]]<=n/2 && n-siz[x]<=n/2 。

例3 POJ 3107 Godfather

题目大意

求树的重心。

思路

这道题和上面的题目几乎完全一样，不在此赘述。

例3 POJ 1155 TELE

思路

树上分组背包。

先初始化点权，叶子结点的点权为顾客愿意付的钱，非叶子结点的点权为 0 。然后将边权化为点权：将每条边深度较大的端点的点权减去边权。

然后通过一趟 bfs 计算每个结点对应的子树包含的叶子数，记录在 siz[] 中。

void dfs1(int x){
	if(head[x] == 0){
		siz[x] = 1;
	}
	for(int i=head[x];i!=0;i=edge[i].next){
		int to =edge[i].to;
		dfs1(to);
		siz[x] += siz[to];
	}
}

定义状态 dp[i][j] 表示：在结点 i 对应的子树选取 j 个顾客，可以获得的最大收益。考虑状态转移，我们会发现对于结点 i 而言，这其实是一个分组背包问题。所以我们要在最外层枚举组，在中间层枚举背包容量，在最内层枚举在当前组选择的顾客数量。

注意初始化 dp[i][0] 的值

void dfs2(int x){
	if(head[x] == 0){
		dp[x][0] = 0;
		dp[x][1] = w[x];
		return;
	}
	dp[x][0] = w[x];
	for(int i=head[x];i!=0;i=edge[i].next){
		int to = edge[i].to;
		dfs2(to);
		for(int j=siz[x];j>=0;j--){
			for(int k=1;k<=min(siz[to],j);k++){
				dp[x][j] = max(dp[x][j], dp[x][j-k]+dp[to][k]);
			}
		}
	}
}

代码

#include<iostream>
#include<cstring>
using namespace std;

const int maxn = 3e3+5;

int n, m;
int dp[maxn][maxn];
int w[maxn];
int siz[maxn];

struct EDGE{
	int to;
	int next;
};
EDGE edge[maxn<<1];
int tot = 0;
int head[maxn];

void addEdge(int fr, int to){
	tot++;
	edge[tot].to = to;
	edge[tot].next = head[fr];
	head[fr] = tot;
}

void dfs1(int x){
	if(head[x] == 0){
		siz[x] = 1;
	}
	for(int i=head[x];i!=0;i=edge[i].next){
		int to =edge[i].to;
		dfs1(to);
		siz[x] += siz[to];
	}
}

void dfs2(int x){
	if(head[x] == 0){
		dp[x][0] = 0;
		dp[x][1] = w[x];
		return;
	}
	dp[x][0] = w[x];
	for(int i=head[x];i!=0;i=edge[i].next){
		int to = edge[i].to;
		dfs2(to);
		// 从大往小推（联系滚动数组）
		for(int j=siz[x];j>=0;j--){
			for(int k=1;k<=min(siz[to],j);k++){
				dp[x][j] = max(dp[x][j], dp[x][j-k]+dp[to][k]);
			}
		}
	}
}

int main(){
	cin>>n>>m;
	memset(dp, 0x80, sizeof(dp));
	for(int i=1;i<=n-m;i++){
		int k;
		cin>>k;
		for(int j=1;j<=k;j++){
			int a, b;
			cin>>a>>b;  
			addEdge(i, a);
			w[a] -= b;
		}
	}
	for(int i=n-m+1;i<=n;i++){
		int a;
		cin>>a;
		w[i] += a;
	}
	dfs1(1);
	dfs2(1);
	for(int i=siz[1];i>=0;i--){
		if(dp[1][i]>=0){
			cout<<i;
			return 0;
		}
	} 
	return 0;
}

例4 HDU 3586 Information Disturbing

题目大意

给定一颗有根树，根结点为 1 ，每条边有边权。问：在删除边的边权总和不超过 m 的前提下，如何选取删除的边才能切断根结点和所有叶子结点的联系，且要求删除边权的最大值最小，输出这个最小值。

思路

二分答案 + 树形dp

二分删除边权的上限 limit，定义 dp[i] 表示：切断结点 i 与其子树上所有叶子结点的联系所需要的最小花费。如果有 dp[1] <= m ，则说明该 limit 可以成立。

代码参考 https://www.cnblogs.com/s1124yy/p/7300957.html

void dfs(int u, int fa, int mid) {
	int flag = 0;
	dp[u] = 0;
	for (int i = head[u]; ~i; i = edges[i].next) {
		int v = edges[i].v;
		int w = edges[i].w;
		if (v == fa) continue;
		flag = 1;
		dfs(v, u, mid);
		if (w > mid) {
			dp[u] += dp[v];
		}
		else {
			dp[u] += min(w, dp[v]);
		}
	}
	if (flag == 0) dp[u] = INF;
}

例5 HDU 5834 Magic boy Bi Luo with his excited tree

题目大意

给定一颗树，每经过边 (u, v) 一次就要支付路费，第一次到达点 i 可以获得收益 v[i]。求从每个点出发的最大收益是多少。

思路

参考：https://www.cnblogs.com/qscqesze/p/5771193.html

7.6 数位DP（P148）

例1 POJ 3254 Corn Fields

7.7 状态压缩DP（P148）

例1 旅行商问题

定义 dp[i][j] 表示：已经访问过的城市的集合为 i ，当前所在城市为 j ，访问所有剩余城市最后回到起点的最小费用。答案对应状态 dp[0][0] 。

dp[(1<<(n+1))-1][0] = 0;
for(int i=(1<<(n+1))-2;i>=0;i--){
	for(int j=0;j<=n;j++){
		for(int k=0;k<=n;k++){
			if(i&(1<<k)) continue;
			if(j == k) continue;
			dp[i][j] = min(dp[i][j], dp[i+(1<<k)][k]+dis[j][k]);
		}
	}
}
cout<<dp[0][0]<<'\n';

例2 POJ 2411 Mondriaan’s Dream

题目大意

用 1*2 的砖块填满一面 n*m 的墙，问有多少种填法。

思路

参考：https://blog.csdn.net/u014634338/article/details/50015825

文章来源:https://blog.csdn.net/MaTF_/article/details/134981556
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！