实验-动态规划（头歌实践教学平台-ACM/ICPC培训）_平台会对你编写的代码进行测试: 测试输入:a[]={1,2,3,4,5},m=5, b[]={2,5
赞
踩
第1关：数塔问题
- 任务描述
- 相关知识
- 编程要求
- 解题思路：
- 测试说明
任务描述
本关任务：编写用动态规划解决数塔问题。
-
相关知识
为了完成本关任务，你需要掌握：动态规划。
编程要求
求上图从顶层到顶层的一个路径，使路径上的数字和最大。要求输出最大的数字和max和数值和最大的路径。
解题思路：
原始信息有层数和数塔中的数据，层数用一个整型变量n存储，数塔中的数据用二维数组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数值和最大的路径是：9->12->10->18->10
测试说明
平台会对你编写的代码进行测试：
测试输入：
5912 1510 6 82 18 9 519 7 10 4 16
输出示例：
max=59数值和最大的路径是：9->12->10->18->10
开始你的任务吧，祝你成功！
- #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("数值和最大的路径是：");
- 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关：最长公共子序列
任务描述
本关任务：编写用动态规划解决最长公共子序列问题。
相关知识
为了完成本关任务，你需要掌握：动态规划。
编程要求
求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列
解题思路：
递推关系分析： 设 A=“a0，a1，…，am−1”，B=“b0，b1，…，bn−1”，Z=“z0,z1,…,zk−1” 为它们的最长公共子序列。 有以下结论： 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]。 由二维数组c的递归定义，c[i][j]的结果依赖于c[i−1][j−1]，c[i−1][j]和c[i][j−1]。可以从c[m][n]开始，跟踪c[i][j]结果的产生过程，从而逆向构造出最长公共子序列。
测试说明
平台会对你编写的代码进行测试：
测试输入：
a=“ABCDBAB”b=“BDCABA”
输出示例：
BCBA
开始你的任务吧，祝你成功！
- #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关：求序列-2 11 -4 13 -5 -2的最大字段和
任务描述
本关任务：编写用动态规划解决最大字段和问题。
相关知识
为了完成本关任务，你需要掌握：动态规划。
编程要求
给定由n个整数（可能为负数）组成的序列：a1,a2,……,an, 求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为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]的定义可知，当b[j−1]>0时b[j]=b[j−1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归表达式为: b[j]=max(b[j−1]+a[j],a[j])，1<=j<=n。
测试说明
平台会对你编写的代码进行测试：
测试输入：
6-2 11 -4 13 -5 -2
输出示例：
20
开始你的任务吧，祝你成功！
- #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关：求最长的单调递增子序列长度
任务描述
本关任务：编写用动态规划解决求最长的单调递增子序列长度问题。
相关知识
为了完成本关任务，你需要掌握：动态规划。
编程要求
给定一个长度为n的数组，找出一个最长的单调递增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为7的数组A5，6，7，1，2，8,9，则其最长的单调递增子序列为5，6，7，8，9，长度为5。求318714101223411624的最长的单调递增子序列长度。
解题思路：
设长度为n的数组为(a[0]，a[1],a[2],...，a[n−1])，则假定以a[j]结尾的数组序列的最长递增子序列长度为L(j)，则L(j)=max(L(i))+1,i<j且a[i]<a[j]。也就是说，我们需要遍历在j之前的所有位置i(从0到j−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
开始你的任务吧，祝你成功！
- #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关：矩阵连乘问题
- 任务描述
- 相关知识
- 编程要求
- 测试说明
-
任务描述
本关任务：编写用动态规划解决矩阵连乘问题。
相关知识
为了完成本关任务，你需要掌握：动态规划。
编程要求
将矩阵连乘积AiAi+1…Aj简记为A[i:j]，其中i<=j。设在矩阵Ak和Ak+1之间将矩阵链断开，则其相应加括号为(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]相乘的计算量。 设计算A[i:j]所需最少乘积数目为，则原问题的最优值为。 当i=j时,a[i:j]=Ai，因此，m[i][j]=0,i=1,⋅⋅⋅,n 当i<j时，m[i][j]=i<k<jmin{m[i][k]+m[k+1][j]+pi−1pkpj} 其中，矩阵Ai的矩阵数为pi−1×pi 矩阵A1的维度：p0p1=3035 矩阵A2的维度：p1p2=3515 矩阵A3的维度：p2p3=155 矩阵A4的维度：p3p4=510 矩阵A5的维度：p4p5=1020 矩阵A6的维度：p5p6=2025 求这6个矩阵连乘的最小相乘次数。
测试说明
平台会对你编写的代码进行测试：
测试输入：
630 3535 1515 55 1010 20-
输出示例： 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 **********/
