【文章內(nèi)容簡介】 你的輸出應該有C行，即每組測試數(shù)據(jù)的輸出占一行，它是計算出的最長公共子序列長度。Sample Input 1ABCBDBA BDCABASample Output 4include include include void prt_lcs(int, int, char [], int**)。int main(int argc, char* argv[]){ char x[100], y[100]。 int i, j, m, n, ** a, ** b。 gets(x)。 gets(y)。 m = strlen(x) + 1。 n = strlen(y) + 1。 if (((a = (int**)malloc(m * sizeof(int*))) == NULL) || ((b = (int**)\ malloc(m * sizeof(int*))) == NULL)) { printf(There is no enough memory!\n)。 exit(1)。 } for (i = 0。 i m。 i ++) if (((a[i] = (int*)malloc(n * sizeof(int))) == NULL) || ((b[i] = \ (int*)malloc(n * sizeof(int))) == NULL)) { printf(There is no enough memory!\n)。 exit(2)。 } for (i = 0。 i m。 i ++) a[i][0] = 0。 for (i = 0。 i n。 i ++) a[0][i] = 0。 for (i = 1。 i m。 i ++) for (j = 1。 j n。 j ++) if (x[i 1] == y[j 1]) { a[i][j] = a[i 1][j 1] + 1。 b[i][j] = 1。 } else if (a[i 1][j] = a[i][j 1]) { a[i][j] = a[i 1][j]。 b[i][j] = 2。 } else { a[i][j] = a[i][j 1]。 b[i][j] = 3。 } printf(%d\n, a[m 1][n 1])。 prt_lcs(m 1, n 1, x, b)。 printf(\n)。 for (i = 0。 i m。 i ++) { free(a[i])。 free(b[i])。 } free(a)。 free(b)。 return 0。}void prt_lcs(int i, int j, char x[], int** b){ if (i 0 || j 0) return。 if (b[i][j] == 1) { prt_lcs(i 1, j 1, x, b)。 printf(%c, x[i 1])。 } else if (b[i][j] == 2) prt_lcs(i 1, j, x, b)。 else prt_lcs(i, j 1, x, b)。}1033 Problem B:MAX SUMDescription 給定由n整數(shù)(可能為負數(shù))組成的序列 {a1,a2,…,an}，求該序列形如ai+ai+1,…,+aj的子段和的最大值。當所有的整數(shù)均為負數(shù)時定義其最大子段和為0。 Input 輸入包含多組測試數(shù)據(jù)。第一行為一個整數(shù)C，表示有C組測試數(shù)據(jù)，接下來有2*C行數(shù)據(jù)，每組測試數(shù)據(jù)占2行，每組測試數(shù)據(jù)第一行是1個整數(shù)n，表示有n個整數(shù),接下來一行有n個整數(shù),它們之間用空格隔開. Output 你的輸出應該有C行，即每組測試數(shù)據(jù)的輸出占一行，它是計算出的最大子段和.Sample Input 162 11 4 13 5 2Sample Output 20include int maxsum(int n,int *a){ int sum=0,b=0,i,j。 for(i=1。i=n。i++) { if(b0) b+=a[i]。 else b=a[i]。 if(bsum) sum=b。 } return sum。}main(){ int m。 scanf(%d,amp。m)。 while(m) { int a[100],i,max,n。 scanf(%d,amp。n)。 for(i=1。i=n。i++) scanf(%d,amp。a[i])。 max=maxsum(n,a)。 printf(%d\n,max)。 }}1034 Problem D:Number TrianglesDescription 給定一個由n行數(shù)字組成的數(shù)字三角形如下圖所示。試設計一個算法，計算出從三角形的頂至底的一條路徑，使該路徑經(jīng)過的數(shù)字總和最大。 編程任務：對于給定的由n 行數(shù)字組成的數(shù)字三角形，編程計算從三角形的頂至底的路徑經(jīng)過的數(shù)字和的最大值。Input 輸入數(shù)據(jù)是由多組測試數(shù)據(jù)組成。第1 行是數(shù)字三角形的行數(shù)n，1≤n≤100。接下來n行是數(shù)字三角形各行中的數(shù)字。所有數(shù)字在0至99之間。Output 對應每組測試數(shù)據(jù)，每行輸出的是計算出的最大值。Sample Input 573 88 1 02 7 4 44 5 2 6 5Sample Output 30include int main(){int inta[102][102]。int i , j 。int n 。// freopen(,r,stdin ) 。while(scanf(%d,amp。n) != EOF ) { for(i = 1 。 i = n 。 i ++ ) for( j =1 。j = i。 j++ ) scanf(%d,amp。inta[i][j] ) 。 for( i = n 1 。 i 0 。 i ) for( j = i 。 j 0 。 j ) { inta[i][j] += inta[i+1][j+1] inta[i+1][j] ? inta[i+1][j+1] : inta[i+1][j]。 } printf(%d\n,inta[1][1] ) 。}return 0 。}1035 編輯距離問題Description 設A 和B 是2 個字符串。要用最少的字符操作將字符串A 轉換為字符串B。這里所說的字符操作包括 (1)刪除一個字符； (2)插入一個字符； (3)將一個字符改為另一個字符。 將字符串A變換為字符串B 所用的最少字符操作數(shù)稱為字符串A到B 的編輯距離，記為d(A,B)。試設計一個有效算法，對任給的2 個字符串A和B，計算出它們的編輯距離d(A,B)。 編程任務： 對于給定的字符串A和字符串B，編程計算其編輯距離d(A,B)。Input 輸入由多組測試數(shù)據(jù)組成。 每組測試數(shù)據(jù)輸入的第1 行是字符串A，第2行是字符串B。Output 對應每組輸入，輸出的每行中的數(shù)是編輯距離d(A,B)。Sample Input fxpimuxwrsSample Output 5include iostreaminclude stringusing namespace std。int main(){ string A1, A2。 cin A1 A2。 int m = ()。 int n = ()。 int *d = new int [n + 1]。 int i 。 for( i = 1。 i = n。 i++) d[i] = i。 for( i = 1。 i = m。 i++) { int y = i 1。 for(int j = 1。 j = n。 j++) { int x = y。 y = d[j]。 int z = j 1 ? d[j 1]:i。 int del = A1[i 1] == A2[j 1] ? 0:1。 d[j] = x + del。 if (d[j] y + 1) d[j] = y + 1。 if (d[j] z + 1) d[j] = z + 1。 } } cout d[n] endl。 return 0。}1036 Pebble MergingDescription 在一個圓形操場的四周擺放著n 堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2 堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試設計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分。 編程任務： 對于給定n堆石子,編程計算合并成一堆的最小得分和最大得分。Input 輸入由多組測試數(shù)據(jù)組成。 每組測試數(shù)據(jù)輸入的第1 行是正整數(shù)n，1≤n≤100，表示有n堆石子。第二行有n個數(shù)，分別表示每堆石子的個數(shù)。Output 對應每組輸入，輸出的第1 行中的數(shù)是最小得分；第2 行中的數(shù)是最大得分。Sample Input 44 4 5 9Sample Output Hint 43 54includeincludeint n。int a[101],s[101][101],t[101][101]。int i,j,k,temp,max,min。int main(){ while(scanf(%d,amp。n)!=1){ i=1。 while(i=n){ scanf(%d,amp。a[i++])。 } memset(t,0,sizeof(t))。 for(i=1。i=n。i++){ for(j=1。j=n。j++){ for(k=i。k=i+j1。k++){ if(kn) temp=k%n。 else temp=k。 t[i][j]+=a[temp]。 } } } memset(s,0,sizeof(s))。 for(j=2。j=n。j++){ for(i=1。i=n。i++){ for(k=1。k=j1。k++){ if(i+kn) temp=(i+k)%n。 else temp=i+k。 max=s[i][k]+s[temp][jk]+t[i][j]。 if(s[i][j]max) s[i][j]=max。 } } } max=0。 for(i=1。i=n。i++){ if(maxs[i][n]) max=s[i][n]。 } memset(s,0,sizeof(s))。 for(j=2。j=n。j++){ for(i=1。i=n。i++){ min=9999999。 for(k=1。k=j1。k++){ if(i+kn) temp=(i+k)%n。 else temp=i+k。 s[i][j]=s[i][k]+s[temp][jk]+t[i][j]。 if(mins[i][j]) min=s[i][j]。 } s[i][j]=min。 } } min=9999999。 for(i=1。i=n。i++){ if(mins[i][n]) min=s[i][n