西安企业网站,做网站要考虑哪些因素,可以免费注册的网站,本科自考多少钱目录 一、数字三角形——算出三角形中的最大路径值
二、最长上升子序列——求一个数组中的最长递增子序列
三、最长公共子序列——求两个字符串中的最长公共子序列 一、数字三角形——算出三角形中的最大路径值
#include iostream
using namespace std;const int N …目录 一、数字三角形——算出三角形中的最大路径值
二、最长上升子序列——求一个数组中的最长递增子序列
三、最长公共子序列——求两个字符串中的最长公共子序列 一、数字三角形——算出三角形中的最大路径值
#include iostream
using namespace std;const int N 500 10;
int a[N][N];int main()
{int n;cin n;// 存储三角形for (int i 0; i n; i )for (int j 0; j i; j )cin a[i][j];// 从三角形的倒二行开始倒着遍历; 对于每一行的每一个元素将该元素左下角和右下角中更大的元素加在其本身上; 比如倒二行的第一个元素4和5中5更大加在2上变成7.for (int i n - 2; i 0; i -- )for (int j 0; j i; j )a[i][j] max(a[i 1][j], a[i 1][j 1]) a[i][j];// 三角形中最大路径值存在(0,0)位置cout a[0][0] endl;return 0;
}
二、最长上升子序列——求一个数组中的最长递增子序列
#include iostream
using namespace std;const int N 1000 10;// a数组存储题目中给定的数组
// f[i]代表以i指针所指元素结尾的上升子序列的长度; f[4]3代表以下标4元素结尾的子序列的长度为3
int a[N], f[N];int main()
{int n;cin n;for (int i 0; i n; i ) cin a[i];// 初始化最长上升子序列的长度为1int ans 1;// 初始化f数组元素全为1for (int i 0; i n; i ) f[i] 1;// 指针i从下标1开始遍历数组for (int i 1; i n; i ){// 指针j从下标0遍历到指针i之前for (int j 0; j i; j )// 如果发现j所指元素小于i所指元素那么可以构成上升子序列更新f[i]if (a[j] a[i]) f[i] max(f[j] 1, f[i]);ans max(ans, f[i]);}cout ans endl;return 0;
}
三、最长公共子序列——求两个字符串中的最长公共子序列
#include iostream
using namespace std;const int N 1000 10;// f[i][j]中的指针i指向s1指针j指向s2f[i][j]代表s1中指针i之前的部分和s2中指针j之前的部分的最长公共子序列的长度; f[7][9]3代表s1中的前7个字符和s2中的前9个字符的最长公共子序列的长度为3
int f[N][N];
int n, m;
string s1, s2;int main()
{cin n m s1 s2;for (int i 1; i n; i )for (int j 1; j m; j )// 如果s1的i-1位等于s2的j-1位那么这一位可以并入s1的前i位和s2的前j位的公共子序列中更新前i位和前j位的最长公共子序列的长度if (s1[i - 1] s2[j - 1]) f[i][j] f[i - 1][j - 1] 1;// 如果不相等一个是i-1一个是j-1求maxelse f[i][j] max(f[i - 1][j], f[i][j - 1]);cout f[n][m] endl;return 0;
}
