首页 > 其他分享 >六、动态规划引入

六、动态规划引入

时间：2024-06-08 23:32:22浏览次数：11  
标签：10 now room int high 引入 动态 规划 dp

动态规划(Dynamic Programming,DP)题是算法竞赛中的必出题型。DP算法的效率高、代码少，竞赛队员不仅需要掌握很多编程技术，而且需要根据题目灵活设计具体的解题方案，能考察其思维力、建模抽象能力、灵活性等。。

和贪心法、分治法一样，DP并不是一个特定的算法，而是一种算法思想。

DP算法思想可以简单解释如下：DP问题一般是多阶段决策问题，它把一个复杂问题分解为相对简单的子问题，再一个个解决，最后得到原复杂问题的最优解；这些子问题是前后相关的，并且非常相似，处理方法几乎一样。把前面子问题的计算结果记录为“状态”,并存储在“状态表”中，后面子问题可以直接查找前面得到的状态表，避免了重复计算，极大地减少了计算复杂度。

DP适用于有重叠子问题和最优子结构性质的问题，具体的解释请参考算法类相关教材。

求解DP问题有3步：

  1. 定义状态
  2. 状态转移
  3. 算法实现
    DP的核心是状态转移方程。用状态转移方程求解状态，状态往往就是问题的解。在DP问题中，只要分析出状态以及状态转移方程，差不多就完成了90%的工作量。

引入

观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 7 → 3 → 8 → 7 → 5 7 \to 3 \to 8 \to 7 \to 5 7→3→8→7→5 的路径产生了最大权值。
输入格式
第一个行一个正整数 r r r ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
对于 100 % 100\% 100% 的数据， 1 ≤ r ≤ 1000 1\le r \le 1000 1≤r≤1000，所有输入在 [ 0 , 100 ] [0,100] [0,100] 范围内。
输出格式
单独的一行,包含那个可能得到的最大的和。
样例输入 #1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出 #1

30

根据题面意思，是要我们找出一条路，既然是找路，那就用搜索呗，搜索深度控制在 r 处结束，每个节点 a [ i ] [ j ] a[i][j] a[i][j] 都有两个岔路： a [ i + 1 ] [ j ] 和 a [ i + 1 ] [ j + 1 ] a[i + 1][j]和a[i + 1][j + 1] a[i+1][j]和a[i+1][j+1]，代码如下：

#include<bits/stdc++.h>  
using namespace std;  
int room[1005][1005];  
int ans = 0, r;  
void dfs(int now_i, int now_j, int sum){  
	if(now_i == r + 1){  
		ans = max(ans, sum);  
		return;  
	}  
	dfs(now_i + 1, now_j, sum + room[now_i][now_j + 1]);  
	dfs(now_i + 1, now_j + 1, sum + room[now_i + 1][now_j + 1]);  
}  
void input(int n){  
	for(int i = 1; i <= n; i++){  
		for(int j = 1; j <= i; j++){  
			cin >> room[i][j];  
		}  
	}  
}  
int main(){  
	cin >> r;  
	input(r);  
	dfs(1, 1, room[1][1]);  
	cout << ans;  
	return 0;  
}

代码看起来很合理，但是在 r 超过20时，需要的运行时间太长了，所以尝试用记忆化搜索来优化，通过设置dp数组： d p [ i ] [ j ] 表示从 r o o m [ i ] [ j ] 到底端的最大权值 dp[i][j]表示从room[i][j]到底端的最大权值 dp[i][j]表示从room[i][j]到底端的最大权值 :

#include<bits/stdc++.h>  
using namespace std;  
int room[1005][1005];  
int dp[1005][1005];  
int  r;  
int dfs(int now_i, int now_j, int sum){  
	if(dp[now_i][now_j] != -1)return dp[now_i][now_j];  
	if(now_i == r + 1)return 0;  
	dp[now_i][now_j] = room[now_i][now_j] + 
			max(dfs(now_i + 1,now_j,sum + room[now_i + 1][now_j]),  
				dfs(now_i + 1,now_j+1,sum + room[now_i + 1][now_j+1]));  
	return dp[now_i][now_j];  
}  
void input(int n){  
	for(int i = 1; i <= n; i++){  
		for(int j = 1; j <= i; j++){  
			cin >> room[i][j];  
		}  
	}  
}  
int main(){  
	cin >> r;  
	memset(dp, -1, sizeof dp);  
	input(r);  
	cout << dfs(1, 1, room[1][1]);  
	return 0;  
}

我们发现：
d p [ i ] [ j ] = r o o m [ i ] [ j ] + m a x ( 左到底，右到底 ) ; dp[i][j] = room[i][j] + max(左到底，右到底); dp[i][j]=room[i][j]+max(左到底，右到底);
这个步骤在倒数第二行的时候会变成：

d p [ i ] [ j ] = r o o m [ i ] [ j ] + m a x ( r o o m [ i + 1 ] [ j ] ,   r o o m [ i + 1 ] [ j + 1 ] ) ; dp[i][j] = room[i][j] + max(room[i + 1][j],\ room[i + 1][j + 1]); dp[i][j]=room[i][j]+max(room[i+1][j], room[i+1][j+1]);
这时候我们会发现我们只要逆推，就可以实现整个程序了：

#include<bits/stdc++.h>  
using namespace std;  
int room[1005][1005];  
void dp(int n){  
	for(int i = n - 1; i >= 1; i--){  
		for(int j = 1; j <= i; j++){  
			room[i][j] += max(room[i + 1][j], room[i + 1][j + 1]);  
		}  
	}  
}  
void input(int n){  
	for(int i = 1; i <= n; i++){  
		for(int j = 1; j <= i; j++){  
			cin >> room[i][j];  
		}  
	}  
}  
int main(){  
	int r; cin >> r;  
	input(r);  
	dp(r);  
	cout << room[1][1];  
	return 0;  
}

01背包问题

还记得上本书的坑吗？背包问题在之前我们用的是贪心法解决，并且我们已经举出了反例，那我们今天就来解决这个问题。
现在你有一个空间为 m 的背包，有 t 件物品，每个物品的体积为 c o s t [ i ] cost[i] cost[i]，价值为 v a l u e [ i ] value[i] value[i]。
现在我们定义一个dp数组 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示在只用了 j 空间，选择第 i 件物品时最多能获得多少钱。
此时会有两个情况：物品 i 放得下 & 物品 i 放不下。如果空间不够放下 i ，那就不选，反之又有两种情况：腾出空间放 i ，还是保持原样不放 i 。即：
$$

\begin{cases}

if\ j < cost[i]\ \ \ dp[\ i\ ][\ j\ ] = dp[\ i-1\ ][\ j\ ]\
\
else\ \ \ dp[\ i\ ][\ j\ ] = max (\ dp[\ i - 1\ ][\ j - cost[\ i\ ]\ ] + value[\ i\ ]，dp[\ i-1\ ][\ j\ ]\ )

\end{cases}
$$
此时 d p [ t ] [ m ] dp[t][m] dp[t][m] 就是最大价值。
假如现在有 10 的空间和 5 个物品，物品信息如下：

nums12345
cost23445
value34451
此时的dp表格图下：
numsj：1j：2j：3j：4j：5j：6j：7j：8j：9j：10
i : 10333333333
i : 20344777777
i : 3034477881111
i : 403457899912
i : 503457899912

结合表格解释一下上面的公式：

  1. 如果此时空间连一个 i 物品都放不下的话，就延续”在这个空间下，没有放这个物品的最佳情况“
  2. 如果这个空间可以放下第 i 个物品，那就有两种选择：在”没有放这个物品的最佳情况中，腾出这个物品的空间，放入这个物品“ 和 ”在这个空间下，不放入这个物品的最佳情况“。
  3. 因为每一行都是最优的情况，所以第 i 行只需要从 i - 1 行考虑就行了。
    代码实现如下：
#include<bits/stdc++.h>  
using namespace std;  
int cost[6] = {0, 2, 3, 4, 4, 5};  
int value[6] = {0,3, 4, 4, 5, 1};  
int dp[20][20];  
int m = 10, t = 5;  
int main(){  
	for(int i = 1; i <= t; i++){  
		for(int j = 1; j <= m; j++){  
			if(j < cost[i])dp[i][j] = dp[i - 1][j];  
			else{  
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + value[i]);  
			}  
		}  
		}  
	cout << dp[t][m];  
	return 0;  
}

此时的dp数组如下：

0    3    3    3    3    3    3    3    3    3
0    3    4    4    7    7    7    7    7    7
0    3    4    4    7    7    8    8    11    11
0    3    4    5    7    8    9    9    12    12
0    3    4    5    7    8    9    9    12    12

那我们怎么样才能知道背包里装了什么呢？由图表来看：

numsj：1j：2j：3j：4j：5j：6j：7j：8j：9j：10
i : 10333333333
i : 20344777777
i : 3034477881111
i : 403457899912
i : 503457899912
  1. 因为 d p [   5   ] [   10   ] = m a x {   d p [   4   ] [   10   ]   ,   d p [   4   ] [   10 − c o s t [   5   ]   ] + v a l u e [   5   ]   } = d p [   4   ] [   10   ] dp[\ 5\ ][\ 10\ ] = max\{\ dp[\ 4\ ][\ 10\ ]\ ,\ dp[\ 4\ ][\ 10 - cost[\ 5 \ ]\ ] + value[\ 5\ ]\ \} = dp[\ 4\ ][\ 10\ ] dp[ 5 ][ 10 ]=max{ dp[ 4 ][ 10 ] , dp[ 4 ][ 10−cost[ 5 ] ]+value[ 5 ] }=dp[ 4 ][ 10 ],
    所以没有选物品5，之后来到 d p [   4   ] [   10   ] dp[\ 4\ ][\ 10\ ] dp[ 4 ][ 10 ]。
  2. 因为 d p [   4   ] [   10   ] = m a x {   d p [ 3 ] [ 10 ]   ,   d p [ 3 ] [   10 − c o s t [   4   ]   ] + v a l u e [ 4 ]   } = d p [ 3 ] [ 10 − c o s t [ 4 ]   ] + v a l u e [ 4 ] dp[\ 4\ ][\ 10\ ] = max\{\ dp[3][10]\ ,\ dp[3][\ 10 - cost[\ 4\ ]\ ] + value[4]\ \} = dp[3][10-cost[4] \ ]+value[4] dp[ 4 ][ 10 ]=max{ dp[3][10] , dp[3][ 10−cost[ 4 ] ]+value[4] }=dp[3][10−cost[4] ]+value[4],说明选了4，之后来到 d p [ 3 ] [ 6 ] dp[3][6] dp[3][6]。
  3. 因为 d p [ 3 ] [ 6 ] = d p [ 2 ] [ 6 ] dp[3][6] = dp[2][6] dp[3][6]=dp[2][6],没选3 ，来到 d p [ 2 ] [ 6 ] dp[2][6] dp[2][6]。
  4. 因为 d p [ 2 ] [ 6 ] = d p [ 1 ] [ 3 ] + c o s t [ 2 ] dp[2][6] = dp[1][3] + cost[2] dp[2][6]=dp[1][3]+cost[2],选了 2，来到 d p [ 1 ] [ 3 ] dp[1][3] dp[1][3]。
  5. 因为 d p [ 1 ] [ 3 ] = d p [ 0 ] [ 1 ] + c o s t [ 1 ] dp[1][3] = dp[0][1] + cost[1] dp[1][3]=dp[0][1]+cost[1];选了1，来到 d p [ 0 ] [ 1 ] dp[0][1] dp[0][1]。
  6. 此时 i = 0，结束。
    代码实现：
int flag[N];  //flag[i] == true 表示选了 i
void Print(int t, int m){  
	memset(flag, false, sizeof flag);  
	int i = t, j = m;  
	while(i != 0){  
		if(dp[i][j] != dp[i -1][j]){  
			i = i - 1;  
		}  
		else{  
			flag[i] = true;  
			j = j - cost[i];  
			i = i - 1;  
		}  
	}  
	for(int i = 0; i < t; i++){  
		if(flag[i])cout << i <<"\t";  
	}  
}

找零问题

如果我们有五种面值的纸币：1、5、10、20、50，凑出m元至少需要几张纸币？
假设我们只有前三张纸币，要凑出11元，

  1. 我们先只用 1 元的纸币，则 i 元需要 i 张纸币：
金额 i01234567891011
张数01234567891011
  1. 在加上 5 元纸币后：
金额 i01234567891011
张数01234567891011
新张012341234523
此时我们发现对于最小张数N，有： N   =   m i n ( N [ i ] ， N [ i − 5 ] + 1 ) N \ =\ min(N[i]，N[i - 5] + 1) N = min(N[i]，N[i−5]+1)。继续加入 10 元纸币：
金额 i01234567891011
张数012341234523
新张012341234512
此时我们发现对于最小张数N，有： N   =   m i n ( N [ i ] ， N [ i − 10 ] + 1 ) N \ =\ min(N[i]，N[i - 10] + 1) N = min(N[i]，N[i−10]+1)。即：
$$
N[i]\ =\ min(\ N[\ i\ ]，N[\ i\ -\ money[\ j\ ]\ ]\ + \ 1)
$$
代码实现：
#include<bits/stdc++.h>  
using namespace std;  
const int N = 1e4 + 7;  
int money[5] = {1,5,10,20,50};  
int dp[N];  //记录最少的张数  
int main(){  
	int n; cin >> n;  
	for(int i = 0; i <= n; i++)dp[i] = i;  
	  //初始化，只用 1 元时
	for(int i = 1; i < 5; i++){//从第二种面值开始凑钱  
		for(int j = money[i]; j <= n; j++){  
			dp[j] = min(dp[j], dp[j - money[i]] + 1);  
		}  
	}  
	cout << dp[n];  
	return 0;  
}

那么新问题又来了，如何输出最少张数的组合呢？
我们可以引入一个 path 数组，path[ i ]记录凑齐 i 元需要的最后一张纸币，再利用 path 倒推即可，例：

cost01234567891011
dp[i]012341234512
path[i]01111555551010
如果此时金额为 7，此时path[ 7 ] = 5，然后查path[7-5] = 1（path[ 2 ] = 1），然后再查path[2 - 1 ],直到查到path[ 0 ]，经过的 path 顺序：5 1 1 便是最小组合。
代码实现查询 x 元的最少纸币组合：
	for(int i = 0; i <= n; i++){
		dp[i] = i;path[i] = 1;
	}  
	for(int i = 1; i < 5; i++){  
		for(int j = money[i]; j <= n; j++){  
			dp[j] = min(dp[j], dp[j - money[i]] + 1);
			path[j] = money[i];  
		}  
	}
	int x;  cin >> x;
	while(x > 0){
		cout << path[ x ] <<" ";
		x = x - path[x];
	}

最长公共子序列（LCS问题）

一个从序列中删去一些元素后得到的序列就是原序列的子序列。
子序列和子串的概念是不一样的，子序列可以不是连续的，但是子串必须是连续的。
现在有两个序列：

  1. X = （a，b，c，f，b，c） 子序列为： X i X_i Xi​

  2. Y = （a，b，f，c，a，b） 子序列为： Y i Y_i Yi​
    我们用 L [ i ] [ j ] L[i][j] L[i][j] 表示 X i  或  Y i X_i\ 或\ Y_i Xi​ 或 Yi​ ，即最长公共子序列。
    现在我们有以下策略：

  3. 如果 X i = Y j X_i=Y_j Xi​=Yj​ ，那就找 X i − 1  和  Y j − 1 X_{i - 1} \ 和 \ Y_{j - 1} Xi−1​ 和 Yj−1​ 的最长公共子序列，然后在其结尾加上 X [ i ] X[i] X[i]。

  4. 如果 X i ≠ Y j X_i \ne Y_j Xi​=Yj​ ，那就找 X i − 1  和  Y j X_{i - 1} \ 和 \ Y_{j} Xi−1​ 和 Yj​ 与 X i  和  Y j − 1 X_{i} \ 和 \ Y_{j - 1} Xi​ 和 Yj−1​ 的最长公共子序列中较大的一个。
    即：
    L [   i   ] [   j   ]   =   { L [   i − 1   ] [   j − 1   ] + 1                               X i = Y j    ,   i > 0    ,   j > 0 m a x (   L [   i − 1   ] [   j   ]   ,   L [   i   ] [   j − 1   ]   )           X i ≠ Y i    ,   i > o    ,   j > 0 L[\ i\ ][\ j \ ]\ =\ \begin{cases} L[\ i - 1\ ][\ j -1\ ] +1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ X_i = Y_j\ \ ,\ i > 0\ \ ,\ j>0 \\ \\ max(\ L[\ i-1\ ][\ j\ ]\ ,\ L[\ i\ ][\ j - 1\ ]\ )\ \ \ \ \ \ \ \ \ X_i \ne Y_i\ \ ,\ i>o\ \ ,\ j>0 \end{cases} L[ i ][ j ] = ⎩ ⎨ ⎧​L[ i−1 ][ j−1 ]+1                             Xi​=Yj​  , i>0  , j>0max( L[ i−1 ][ j ] , L[ i ][ j−1 ] )         Xi​=Yi​  , i>o  , j>0​
    下面列表说明：

  5. 求 L [ 1 ] [ 1 ] L[1][1] L[1][1] ，有 X 1 = Y 1 X_1 = Y_1 X1​=Y1​ ；此时有： L [ 1 ] [ 1 ] = L [ 0 ] [ 0 ] + 1 L[1][1] = L[0][0] + 1 L[1][1]=L[0][0]+1 ：

L [ i ] [ j ] L[i][j] L[i][j]Y=abfcab
X=0123456
a11
b2
  1. 求 L [ 1 ] [ 2 ] L[1][2] L[1][2] ，有 X 1 ≠ Y 2 X_1 \ne Y_2 X1​=Y2​ ，此时： L [ 1 ] [ 2 ] = m a x   { L [ i ] [ i ]   ,   L [ 0 ] [ 2 ] }   =   1 L[1][2] = max\ \{L[i][i]\ ,\ L[0][2]\}\ =\ 1 L[1][2]=max {L[i][i] , L[0][2]} = 1 :
L [ i ] [ j ] L[i][j] L[i][j]Y=abfcab
X=0123456
a111
b2
  1. 由此继续：补充完表格：
L [ i ] [ j ] L[i][j] L[i][j]Y=abfcab
X=0123456
a1111111
b2122222
c3122333
f4123333
b5123334
c6123444
此时 L [ 6 ] [ 6 ] L[6][6] L[6][6] 就是答案。
代码实现：
#include<bits/stdc++.h>  
using namespace std;  
const int N = 1e3 + 7;  
string str1, str2;  
int dp[N][N], len1, len2;  
int LCS(){  
	memset(dp, 0, sizeof dp);
	for(int i = 1; i <= len1; i++){  
		for(int j = 1; j <= len2; j++){  
			if(str1[i - 1] == str2[j - 1]){  
				dp[i][j] = dp[i - 1][j - 1] + 1;  
			}  
			else{  
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  
			}  
		}  
	}  
	return dp[len1][len2];  
}
int main(){  
	while(cin >> str1 >> str2){  
		len1 = str1.size();  
		len2 = str2.size();  
		cout << LCS() << endl;  
	}  
	return 0;  
}

打印最长公共子序列的逻辑和01背包输出类似，可以自行尝试。

最长递增子序列（LIS问题）

怎样找出一个序列最长的递增子序列呢？
有两个办法：

  1. 对序列排序，用新序列与原序列求LCS。
  2. 动态规划，用dp{ i }，表示以第 i 个数字结尾的递增子序列长度，然后max{ d p [ i ] dp[i] dp[i] }就是。
  3. 利用递增子序列的性质
    1 不做解释，2 代码如下：
#include<bits/stdc++.h>  
using namespace std;  
const int N = 1e3 + 7;  
int arr[N], dp[N];  
int n;  
int LIS(int len){  
	for(int i = 1; i <= len; i++){  
		cin >> arr[i];  
	}  
	for(int i = 1; i <= n; i++){  
		int cnt = 0, maxx = arr[i];  
		for(int j = 1; j <= i; j++){  
			if(arr[j] < maxx)cnt++;  
		}  
		dp[i] = cnt;  
	}  
	int maxx = 0;  
	for(int i = 0; i <= len; i++){  
		maxx = max(maxx, dp[i]);  
	}  
	return maxx;  
}  
int main(){  
	while(cin >> n){  
		cout << LIS(n) << endl;  
	} 
	return 0; 
}

2 方法的复杂度是 O ( N 2 ) O(N^2) O(N2)，效率还是不够高，我们考虑用 3 降低复杂度至 O ( N l o g 2 N ) O(Nlog_{2}N) O(Nlog2​N)。方法如下：

  1. 定义 d [   ] d[\ ] d[ ] , l e n len len , A [   ] A[\ ] A[ ]； d [   ] d[\ ] d[ ]记录最长子序列的内容， l e n len len 记录 d [   ] d[\ ] d[ ] 的长度， A [   ] A[\ ] A[ ]表示原序列
  2. d [ 1 ] = A [ 1 ] ； l e n = 1 d[1] = A[1]；len = 1 d[1]=A[1]；len=1；
  3. 对 A [   ] A[\ ] A[ ]里的数字逐个处理，如果大于 d [   ] d[\ ] d[ ]的最后一个，那就把这个数字放在 d [   ] d[\ ] d[ ]的最后面，反之，则把用这个数字替换掉序列中第一个大于它的数字。
    为什么 d [   ] d[\ ] d[ ]的长度等于 h i g h [   ] high[\ ] high[ ]的LIS的长度?
    分析算法对 h i g h [   ] high[\ ] high[ ]的两个关键操作：
  4. 如果 h i g h [ k ] high[k] high[k]比 d [   ] d[\ ] d[ ]末尾的数字更大，就加到 d [   ] d[\ ] d[ ]后面， h i g h [   ] high[\ ] high[ ]的LIS加1， d [   ] d[\ ] d[ ]的长度加1。
  5. 如果 h i g h [ k ] high[k] high[k]比 d [   ] d[\ ] d[ ]末尾的数字小，就替换 d [   ] d[\ ] d[ ]中第1个大于它的数字”，有两个作用：首先，这个操作不影响LIS的长度，也不影响 d [   ] d[\ ] d[ ]的长度；其次， h i g h [   ] high[\ ] high[ ]后面还没有处理的数很多都比已经处理过的数小，但是有可能序列更长，这里的替换给后面更小的数字留下了机会。为什么用 h i g h [ k ] high[k] high[k]替换 d [   ] d[\ ] d[ ]中第1个比它大的数字?因为数字 h i g h [ k ] high[k] high[k]可能在LIS中，而被它替换的数字由于更大，不在LIS中的可能性更大。
    假设 h i g h [   ]   =   {   4 ， 8 ， 9 ， 5 ， 6 ， 7   } high[\ ]\ =\ \{\ 4，8，9，5，6，7\ \} high[ ] = { 4，8，9，5，6，7 }
    如下表：
i i i h i g h [   ] high[\ ] high[ ] d [   ] d[\ ] d[ ] l e n len len 说明 说明 说明
1 1 14，8，9，5，6，741初始 d [ 1 ] = h i g h [ 1 ] d[1]=high[1] d[1]=high[1]
2 2 24，8，9，5，6，74，82 h i g h [ 2 ] > d [ 1 ] ，加到 d [   ] 后面 high[2]>d[1]，加到d[\ ]后面 high[2]>d[1]，加到d[ ]后面
3 3 34，8，9，5，6，74，8，93 d [   ] 后面加上 9 d[\ ]后面加上9 d[ ]后面加上9
4 4 44，8，9，5，6，74，5，935比d末尾的9小,用5替换d中第1个比5大的数:8
5 5 54，8，9，5，6，74，5，63 用 6 替换 9 用6替换9 用6替换9
6 6 64，8，9，5，6，74，5，6，74 d [   ] 后面加上 7 d[\ ]后面加上7 d[ ]后面加上7
现在怎么找到第一个比 h i g h [ k ] high[k] high[k]大的数？还记得二分法吗？
代码如下：
#include<bits/stdc++.h>  
using namespace std;  
const int N = 1e3 + 7;  
int high[N], d[N];  
int len = 1;  
void input(int n){  
	for(int i = 1; i <= n; i++){  
		cin >> high[i];  
	}  
	d[1] = high[1];  
}  
int b_search(int*arr, int left, int right, int aim) {  
	while (left < right) {  
		int mid = left + (right - left) / 2;  
		if (arr[mid] >= aim)right = mid;  
		else left = mid + 1;  
	}  
	return right;  
}  
void LIS(int n){  
	for(int i = 2; i <= n; i++){  
		if(high[i] > d[len]){  
			len++;  
			d[len] = high[i];  
		}  
		else{  
			int loc = b_search(d, 0, len + 1, high[i]);  
			d[loc] = high[i];  
		}      
	}  
	for(int i = 1; i <= len; i++){  
		cout << d[i] << " ";  
	}  
}  
int main(){  
	int n;  
	while(cin >> n){  
		input(n);  
		LIS(n);  
	}  
	return 0;  
}

标签：10,now,room,int,high,引入,动态,规划,dp
From： https://blog.csdn.net/n666fgh/article/details/139552771

相关文章

  • SpringAOP-代理方式-Cglib动态代理
    文章目录cglib动态代理cglib是基于继承的方式实现的是继承目标类从而产生代理类springaop底层使用的就是cglib的动态代理packagecom.itheima.cjlibproxy;importnet.sf.cglib.proxy.Callback;importnet.sf.cglib.proxy.Enhancer;importnet.sf.cglib.proxy.......
  • tools maven引入 maven tools.jar
    怎么用javadoc和Doclet配合解析自己想要的注释（链接）。既然是一个工具，自然就要生成可执行的jar包。这貌似是一个很合理的要求，然后坑就来了。我上篇说的是直接复制的tool.jar到lib包下面，添加进资源包就可以了，但是maven项目肯定不能这样做的，这样不规范。我在网上去搜索了tools.jar的......
  • 再探堆栈欺骗之动态欺骗
    本文首发先知社区：https://xz.aliyun.com/t/14542在上篇文章https://xz.aliyun.com/t/14487中，我们讨论了静态堆栈欺骗，那是关于hooksleep，在睡眠期间改变堆栈行为的欺骗，这篇文章我们来一起讨论一下主动欺骗，允许任意函数发起时的堆栈欺骗。相关的基础知识在上篇文章已经介绍，并......
  • hdu1087简单动态规划
    求最长子序列的和。dp[i]=max(dp[i],dp[j]+xx[i])。importjava.util.Arrays;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){//TODO自动生成的方法存根Scannersc=newScanner(System.in);......
  • Spring AOP（实现，动态原理）详解版
    SpringAOP1.什么是AOP？1.1引入AOP依赖1.2编写AOP程序2.SpringAOP核⼼概念2.1切点(Pointcut)2.2连接点(JoinPoint)2.3通知(Advice)2.4切⾯(Aspect)3.通知类型3.1顺序3.2切⾯优先级@Order3.3⾃定义注解@MyAspect4.SpringAOP原理5动态代理怎么实现5.1JDK动......
  • vsCode开发实战之 C语言动态文件通讯录项目
    引言本项目所用开发环境为vsCode+CMake，至于为何如此选择，我就不赘述了，希望这篇博客能对您的学习有帮助！看完记得点赞收藏哦！！！一.项目结构项目根目录下结构如图：二.CMake配置CMake文件配置如图：三.头文件contact.h四.主函数文件main.c五.接口函数文件contact.c ......
  • SpringBoot高手之路jdk动态代理
    文章目录JDK动态代理基于jdk的动态代理Aop底层就是基于动态代理实现的实现代码先写代理对象工具JDK动态代理基于jdk的动态代理业务需求通过动态代理技术,对service层的方法统计执行时间–创建代理对象Aop底层就是基于动态代理实现的jdk动态代理技术是基于接口......
  • 通过site 包加载egg 或者whl pcakge 包并动态调用模块方法
    以前简单说过通过sys.path进行egg文件模块的加载，实际上我们可以结合site以及.pth能力，实现灵活的加载处理，同时通过importlib进行动态加载，以下是一个简单说明加载配置通过site包，添加自定义目录，目录里边包含.pth配置目录结构.pth内容使用核心是通过site添加......
  • 【YOLOv8改进】CPCA(Channel prior convolutional attention)中的通道注意力,增强特征
    YOLO目标检测创新改进与实战案例专栏专栏目录：YOLO有效改进系列及项目实战目录包含卷积，主干注意力，检测头等创新机制以及各种目标检测分割项目实战案例专栏链接:YOLO基础解析+创新改进+实战案例摘要医学图像通常展示出低对比度和显著的器官形状变化等特征。现有注意......
  • 计算机网络实验二：动态路由配置
    这个是pkt文件https://pan.quark.cn/s/5a80aa8a21f7发现复制不来图片把实验报告也放在夸克网盘大家自行下载https://pan.quark.cn/s/1d9ea9d31bea有兴趣的可以一点一点跟着做没兴趣的自行下载提交（手动狗头）实验报告里面有私货记得删除修改这个pkt文件我没有配置协......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99