第1關(guān)：數(shù)塔問題
- 任務(wù)描述
- 相關(guān)知識
- 編程要求
- 解題思路：
-
測試說明
任務(wù)描述
本關(guān)任務(wù)：編寫用動態(tài)規(guī)劃解決數(shù)塔問題。
-
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：動態(tài)規(guī)劃。
編程要求
求上圖從頂層到頂層的一個路徑，使路徑上的數(shù)字和最大。要求輸出最大的數(shù)字和max和數(shù)值和最大的路徑。
解題思路：
原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個整型變量n存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組data，存儲成如下的下三角陣:
912 1510 6 82 18 9 519 7 10 4 16d[n][j]=data[n][j]， j=1,2,……,n；d[i][j]=max(d[i+1][j]，d[i+1][j+1])+data[i][j]， i=n-1,n-2,……1，j=1,2,……,i5912 1510 6 82 18 9 519 7 10 4 16max=59數(shù)值和最大的路徑是：9->12->10->18->10
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：文章來源：http://www.zghlxwxcb.cn/news/detail-766401.html
5912 1510 6 82 18 9 519 7 10 4 16
輸出示例：
max=59數(shù)值和最大的路徑是：9->12->10->18->10
開始你的任務(wù)吧，祝你成功！
#include <stdio.h>
int main(){
int a[50][50][4],i,j,n;
// printf("Please input the number of rows:\n");
// scanf("%d",&n);
n = 5;
i=1;
a[1][1][1]=9;
a[2][1][1]=12, a[2][2][1]=15;
a[3][1][1]=10, a[3][2][1]=6, a[3][3][1]=8;
a[4][1][1]=2, a[4][2][1]=18, a[4][3][1]=9, a[4][4][1]=5;
a[5][1][1]=19, a[5][2][1]=7, a[5][3][1]=10, a[5][4][1]=4, a[5][5][1]=16;
for(i=1;i<=n;i++)
for(j=1; j<=i; j++)
{
a[i][j][2]=a[i][j][1];
a[i][j][3]=0;
}
for(i=n-1; i>=1; i--)
for(j=1; j<=i; j++)
if(a[i+1][j][2]>a[i+1][j+1][2])
{
a[i][j][2] = a[i][j][2] + a[i+1][j][2];
a[i][j][3] = 0;
}
else
{
a[i][j][2] = a[i][j][2] + a[i+1][j+1][2];
a[i][j][3] = 1;
}
printf("max=%d\n",a[1][1][2]);
printf("數(shù)值和最大的路徑是：");
j=1;
for(i=1;i<=n-1;i++)
{
printf("%d->",a[i][j][1]);
j = j+a[i][j][3];
}
printf("%d\n\n\n",a[n][j][1]);
return 0;
}第2關(guān)：最長公共子序列
- 任務(wù)描述
- 相關(guān)知識
- 編程要求
- 解題思路：
- 測試說明
任務(wù)描述
本關(guān)任務(wù)：編寫用動態(tài)規(guī)劃解決最長公共子序列問題。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：動態(tài)規(guī)劃。
編程要求
求字符串序列“ABCDBAB”和“BDCABA”的最長公共子序列
解題思路：
遞推關(guān)系分析： 設(shè) A=“a0，a1，…，am?1”，B=“b0，b1，…，bn?1”，Z=“z0,z1,…,zk?1” 為它們的最長公共子序列。 有以下結(jié)論： 1）如果am?1=bn?1,則zk?1=am?1=bn?1,且“z0,z1,…,zk?2”是“a0,a1,…,am?2”和“b0,b1,…,bn?2”的一個最長公共子序列； 2）如果am?1?=bn?1，則若zk?1?=am?1，蘊涵“z0，z1，…，zk?1”是“a0,a1,…,am?2”和“b0,b1,…,bn?1”的一個最長公共子序列； 3）如果am?1?=bn?1，則若zk?1?=bn?1，蘊涵“z0，z1，…，zk?1”是“a0，a1，…，am?1”和“b0，b1，…，bn?2”的一個最長公共子序列。 定義c[i][j]為序列“a0,a1,…,ai?1”和“b0,b1,…,bj?1”的最長公共子序列的長度，計算c[i][j]可遞歸地表述如下： 1）c[i][j]=0 如果i=0或j=0； 2）c[i][j]=c[i?1][j?1]+1 如果i,j>0,且a[i?1]=b[j?1]； 3）c[i][j]=max(c[i][j?1],c[i?1][j]) 如果i,j>0,且a[i?1]?=b[j?1]。 由二維數(shù)組c的遞歸定義，c[i][j]的結(jié)果依賴于c[i?1][j?1]，c[i?1][j]和c[i][j?1]?？梢詮腸[m][n]開始，跟蹤c[i][j]結(jié)果的產(chǎn)生過程，從而逆向構(gòu)造出最長公共子序列。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
a=“ABCDBAB”b=“BDCABA”
輸出示例：
BCBA
開始你的任務(wù)吧，祝你成功！
#include "stdio.h"
#include "string.h"
char a[1000]="ABCDBAB";
char b[1000]="BDCABA";
char str[100];
int c[100][100];
int lcs_len()
{
int m,n,i,j,lcs;
m = strlen(a);
n = strlen(b);
for(i=0;i<=m;i++) c[i][0]=0;
for(i=0;i<=n;i++) c[0][i]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(a[i-1]==b[j-1])
c[i][j] = c[i-1][j-1]+1;
else if(c[i-1][j]>=c[i][j-1])
c[i][j] = c[i-1][j];
else
c[i][j] = c[i][j-1];
}
lcs = c[m][n];
return lcs;
}
void build_lcs()
{
int k,i=strlen(a),j=strlen(b);
k = lcs_len();
str[k]=' ';
while(k>0)
if(c[i][j]==c[i-1][j])
i=i-1;
else if(c[i][j]==c[i][j-1])
j=j-1;
else
{
k=k-1;
str[k]=a[i-1];
j=j-1;
}
}
int main()
{
build_lcs();
printf("%s",str);
return 0;
}第3關(guān)：求序列-2 11 -4 13 -5 -2的最大字段和
- 任務(wù)描述
- 相關(guān)知識
- 編程要求
- 解題思路：
- 測試說明
任務(wù)描述
本關(guān)任務(wù)：編寫用動態(tài)規(guī)劃解決最大字段和問題。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：動態(tài)規(guī)劃。
編程要求
給定由n個整數(shù)（可能為負(fù)數(shù)）組成的序列：a1,a2,……,an, 求該序列的最大子段和。當(dāng)所有整數(shù)均為負(fù)數(shù)，定義其最大子段和為0。
解題思路：
定義b[j]=max(a[i]+a[i+1]+…+a[j])，其中1<=i<=j，并且1<=j<=n。那么所求的最大子段和可以表示為max b[j]，1<=j<=n。 由b[j]的定義可知，當(dāng)b[j?1]>0時b[j]=b[j?1]+a[j]，否則b[j]=a[j]。故b[j]的動態(tài)規(guī)劃遞歸表達式為: b[j]=max(b[j?1]+a[j],a[j])，1<=j<=n。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
6-2 11 -4 13 -5 -2
輸出示例：
20
開始你的任務(wù)吧，祝你成功！
#include <stdio.h>
int maxsubsequence(int n,int a[],int b[],int max)
{
for (int i = 0; i < n; i++)
{
if (i == 0)
{
b[i] = a[i];
max = b[i];
}
else
{
if (b[i - 1] <= 0)
b[i] = a[i];
else
b[i] = b[i - 1] + a[i];
if (b[i] > max)
max = b[i];
}
}
return max;
}
int main()
{
int n;
scanf("%d",&n);
int a[1000];
for (int i = 0; i < n; i++)
scanf("%d",&a[i]);
int b[100],max = 0;
max = maxsubsequence(n, a, b, max);
printf("%d",max);
}第4關(guān)：求最長的單調(diào)遞增子序列長度
- 任務(wù)描述
- 相關(guān)知識
- 編程要求
- 解題思路：
- 測試說明
任務(wù)描述
本關(guān)任務(wù)：編寫用動態(tài)規(guī)劃解決求最長的單調(diào)遞增子序列長度問題。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：動態(tài)規(guī)劃。
編程要求
給定一個長度為n的數(shù)組，找出一個最長的單調(diào)遞增子序列（不一定連續(xù)，但是順序不能亂）。例如：給定一個長度為7的數(shù)組A5，6，7，1，2，8,9，則其最長的單調(diào)遞增子序列為5，6，7，8，9，長度為5。求318714101223411624的最長的單調(diào)遞增子序列長度。
解題思路：
設(shè)長度為n的數(shù)組為(a[0]，a[1],a[2],...，a[n?1])，則假定以a[j]結(jié)尾的數(shù)組序列的最長遞增子序列長度為L(j)，則L(j)=max(L(i))+1,i<j且a[i]<a[j]。也就是說，我們需要遍歷在j之前的所有位置i(從0到j(luò)?1)，找出滿足條件a[i]<a[j]的L(i)，求出max(L(i))+1即為L(j)的值。最后，我們遍歷所有的L(j)（從0到n?1），找出最大值即為最大遞增子序列。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
103 18 7 14 10 12 23 41 16 24
輸出示例：
6
開始你的任務(wù)吧，祝你成功！
#include <stdio.h>
/********** Begin **********/
int main(){
int n;
scanf("%d",&n);
int m[n][3];
m[0][1]=1;
m[0][2]=0;
for(int i=0;i<n;i++){
scanf("%d",&m[i][0]);
if(i!=0){
m[i][1]=0;
int k=i-1;
while(k>=0){
if(m[i][0]>m[k][0]){
if(k==i-1){
m[i][1]=m[k][1]+1;
m[i][2]=k;
}
else{
int max=m[k][1]+1;
if(max>m[i][1]){
m[i][1]=max;
m[i][2]=k;
}
}
}
k--;
}
if(k<0&&m[i][1]==0){
m[i][1]=1;
m[i][2]=i;
}
}
}
int max=m[0][1],j=0;
for(int i=0;i<n;i++){
if(m[i][1]>=max){
max=m[i][1];
j=i;
}
}
printf("%d\n",max);
}
/********** End **********/
-
第5關(guān)：矩陣連乘問題
- 任務(wù)描述
- 相關(guān)知識
- 編程要求
- 測試說明
-
任務(wù)描述
本關(guān)任務(wù)：編寫用動態(tài)規(guī)劃解決矩陣連乘問題。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：動態(tài)規(guī)劃。
編程要求
將矩陣連乘積AiAi+1…Aj簡記為A[i:j]，其中i<=j。設(shè)在矩陣Ak和Ak+1之間將矩陣鏈斷開，則其相應(yīng)加括號為(AiAi+1…Ak) (Ak+1Ak+2…Aj)。A[i:j]的計算量等于三部分計算量之和： （1）A[i:k]的計算量， （2）A[k+1:j]的計算量， （3）A[i:k]與A[k+1:j]相乘的計算量。 設(shè)計算A[i:j]所需最少乘積數(shù)目為，則原問題的最優(yōu)值為。 當(dāng)i=j時,a[i:j]=Ai?，因此，m[i][j]=0,i=1,???,n 當(dāng)i<j時，m[i][j]=i<k<jmin?{m[i][k]+m[k+1][j]+pi?1?pk?pj?} 其中，矩陣Ai?的矩陣數(shù)為pi?1?×pi? 矩陣A1?的維度：p0?p1?=3035 矩陣A2?的維度：p1?p2?=3515 矩陣A3?的維度：p2?p3?=155 矩陣A4?的維度：p3?p4?=510 矩陣A5?的維度：p4?p5?=1020 矩陣A6?的維度：p5?p6?=2025 求這6個矩陣連乘的最小相乘次數(shù)。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
630 3535 1515 55 1010 20-
輸出示例：文章來源地址http://www.zghlxwxcb.cn/news/detail-766401.html m[1][6]=1512520 25-
#include <stdio.h> #include <stdlib.h> /********** Begin **********/ int main(){ int n; scanf("%d",&n); int a[n][2]; int b[n][n]={0}; for(int i=0;i<n;i++){ scanf("%d %d",&a[i][0],&a[i][1]); } for(int i=1;i<n;i++){ for(int j=0;j<n-i;j++){ b[j][j+i]=b[j][j]+b[j+1][j+i]+a[j][0]*a[j][1]*a[j+i][1]; int k=j+1; for(;k<j+i;k++){ int t=b[j][k]+b[k+1][j+i]+a[j][0]*a[k][1]*a[j+i][1]; if(t<b[j][j+i]) { b[j][j+i]=t; } } } } printf("m[%d][%d]=%d",1,n,b[0][n-1]); return 0; } /********** End **********/
到了這里，關(guān)于實驗-動態(tài)規(guī)劃（頭歌實踐教學(xué)平臺-ACM/ICPC培訓(xùn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
