6107、
題目內容:
问题描述：
给定两个序列X={x1,x2,...,xm}和Y={y1,y2,...,yn},找出X和Y的最长公共子序列。
输入：
第1行：两个子序列的长度，m n
第2行：第1个子序列的各个元素（序列下标从1开始）
第3行：第2个子序列的各个元素（序列下标从1开始）
输出：
最长公共子序列
实例：
输入：
第1行：
4 5 //m和n的值
第2行
abad //输入4个字符，下标从1开始
第3行
baade //输入5个字符，下标从1开始
输出：
aad
#include<iostream> using namespace std; const int maxn=105; int c[maxn][maxn];//c[i][j]记录的是a[:i]和b[:j]的最长公共子序列的长度 int d[maxn][maxn];//最长公共子序列的来源，以便最后得到最长公共子序列 string a,b; void lcslength(){int length1=a.size();int length2=b.size();for(int i=0;i<length1;i++){c[i][0]=0;d[i][0]=0;}for(int j=0;j<length2;j++){c[0][j]=0;d[0][j]=0;}for(int i=1;i<=length1;i++){for(int j=1;j<=length2;j++){if(a[i-1]==b[j-1]){c[i][j]=c[i-1][j-1]+1;d[i][j]=1;//表示最长子序列长度由左上角一位加1得到}else{if(c[i][j-1]>c[i-1][j]){c[i][j]=c[i][j-1];d[i][j]=2;//表示从左侧而来}else{c[i][j]=c[i-1][j];d[i][j]=3;//表示从上侧而来}}}} } void output(int i,int j){if(i==0||j==0){return ;}if(d[i][j]==1){output(i-1,j-1);cout<<a[i-1];}else if(d[i][j]==2){output(i,j-1);}else{output(i-1,j);} } int main(){int n,m;cin>>n>>m;cin>>a>>b;lcslength();output(a.size(),b.size());}
6106、
題目內容:
问题描述：给定一个由n行数字组成的数字三角形，如下图所示，试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
算法设计：对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
数据输入：第1行是数字三角形的行数n，接下来n行是数字三角形各行中的数字。
结果输出：数字和的最大值及最大值由哪些数字的和组成。
实例：
输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出：
30
7 3 8 7 5
#include<iostream> using namespace std; const int N=105; int dp[N][N]; int sum[N][N]; int main(){int n;cin>>n;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){cin>>dp[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<=i;j++){sum[i][j]=dp[i][j];}}for(int i=n-2;i>=0;i--){for(int j=0;j<=i;j++){//从小往上推sum[i][j]+=max(sum[i+1][j+1],sum[i+1][j]);}}cout<<sum[0][0]<<endl;int k=0;for(int i=0;i<n;i++){cout<<dp[i][k]<<" ";if(dp[i][k]+sum[i+1][k]<dp[i][k]+sum[i+1][k+1]){//从上往下推k+=1;}} }