程序设计基础II-实验6 动态规划
7-1 数字三角形问题
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
输入格式:
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。
输出格式:
输出数据只有一个整数，表示计算出的最大值。
输入样例:
在这里给出一组输入。例如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
#include <stdio.h>
#include <stdlib.h>
int main()
{
int j,n,i,d[101][101],a[101][101];
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&d[i][j]);
for(j=1;j<=n;j++)
a[n][j]=d[n][j];
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
{
if(a[i+1][j]>a[i+1][j+1])
a[i][j]=a[i+1][j]+d[i][j];
else a[i][j]=a[i+1][j+1]+d[i][j];
}
printf("%d\n",a[1][1]);
return 0;
}
7-2 小鑫去爬山
马上就要放假了，小鑫打算去爬山。
小鑫要去爬的这座山有n个海拔区间。为了清楚描述我们可以从上到下标号1到n。
第i个区间有i个落脚点，每一个落脚点都有一个危险值。
小鑫需要在第n个海拔区间挑选一个点向上爬，爬到第1个海拔区间（也就是山顶）。他必须规划一条路径，让危险值之和最小。这样才安全的。
并不是任意两个落脚点之间都可以相互到达。我们这样定义对于第i个（i<n）区间的第j个落脚点，只有第i+1个区间的第j个和第j+1个可以到达。
你能帮助他找到最安全的路么？
输入格式:
输入数据为多组，到文件结束。
对于每一组数据，第一行有一个数，为n 。n≤100;
接下来有n行，第i行有i个数。代表第i个区间i个落脚点的危险值。
所有数据均在int范围内。
输出格式:
对于每组数据，输出一行一个数，为答案。
输入样例:
在这里给出一组输入。例如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
17
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,i,j;
int a[101][101],b[101][101];
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=1;i<=n;i++)
{
b[n][i]=a[n][i];
}
for(i=n-1;i>=1;i--)
{
for(j=1;j<=i;j++)
{
if(b[i+1][j]<b[i+1][j+1])b[i][j]=b[i+1][j]+a[i][j];
else b[i][j]=b[i+1][j+1]+a[i][j];
}
}
printf("%d\n",b[1][1]);
}
return 0;
}
7-3 最长公共子序列问题
给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
输入格式:
输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。
输出格式:
每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。
输入样例:
ABCBDAB
BDCABA
输出样例:
4
#include <stdio.h>
#include <string.h>
#define N 510
int i,j,len1,len2,c[N][N];
char x[N],y[N];
int main()
{
while(scanf("%s %s",x,y)!=EOF){
len1=strlen(x);
len2=strlen(y);
for(i=0;i<=len1;i++)
{c[i][0]=0;}
for(j=0;j<=len2;j++) {c[0][j]=0;}
for(i=1;i<=len1;i++){
for(j=1;j<=len2;j++)
{
if(x[i-1]==y[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];}
}
}}
printf("%d\n",c[len1][len2]); }
return 0;
}
7-4 最长公共子序列
从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下地字符按原来顺序组成的串。例如：“ ”，“a”，“xb”，“aaa”，“bbb”，“xabb”，“xaaabbb”都是串“xaaabbb”的子序列。（例子中的串不包含引号。）
编程求N个非空串的最长公共子序列的长度。限制：2<=N<=100；N个串中的字符只会是数字0，1，…，9或小写英文字母a，b，…，z；每个串非空且最多含100个字符；N个串的长度的乘积不会超过30000。
输入格式:
文件第1行是一个整数T，表示测试数据的个数（1<=T<=10）。接下来有T组测试数据。各组测试数据的第1行是一个整数Ni，表示第i组数据中串的个数。各组测试数据的第2到N+1行中，每行一个串，串中不会有空格，但行首和行末可能有空格，这些空格当然不算作串的一部分。
输出格式:
输出T行，每行一个数，第i行的数表示第i组测试数据中Ni个非空串的最长公共子序列的长度。
输入样例:
1
3
ab
bc
cd
输出样例:
0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char a[110][110];//二维字符数组保存字符
int d[30010];
int len[110];//一维len保存每个字符数组的长度
int n;
int f(int l[])
{
int i, j, index, ret, t;
for (i = 1; i <= n; i++)
if (l[i] == 0)//判断字符长的是否为0,为0直接以0退出
return 0;
//-------------------------------------------------------------
for (index = l[n] - 1, i = n - 1; i >= 1; i--)
index = index * len[i] + l[i] - 1;//转化为一维数组，原理有待考究（对我来说）
if (d[index] >= 0)
return d[index];//一但有值，直接返回
//-------------------------------------------------------------
for (i = 2; i <= n; i++)
if (a[1][l[1] - 1] != a[i][l[i] - 1])
break;//在看每个字符串的末尾（我当时看错了，，以为是倒数第二）
if (i > n)//字符串末尾全相同
{
for (j = 1; j <= n; j++)
l[j]--;
ret = f(l) + 1;
for (j = 1; j <= n; j++)
l[j]++;//记得恢复
}
else//有不同，递归
{
ret = 0;
for (j = 1; j <= n; j++)
{
l[j]--;//感觉类似于dfs,历遍了
t = f(l);
if (t > ret)
ret = t;
l[j]++;
}
}
d[index] = ret;
return ret;
}
//-------------------------------------------------------------
int main()
{
int T, i;
int l[110];//保存多维字符数组长度的动态变化
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%s", a[i]);
len[i] = strlen(a[i]);
l[i] = strlen(a[i]);
}
memset(d, -1, sizeof(d));
printf("%d\n", f(l));
}
return 0;
}
7-5 最长上升子序列
一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1<= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
输入格式:
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出格式:
最长上升子序列的长度。
输入样例:
在这里给出一组输入。例如：
7
1 7 3 5 9 4 8
输出样例:
在这里给出相应的输出。例如：
4
#include<stdio.h>
#define MAX_N 1005
int dp[MAX_N];
int main() {
int n, a[MAX_N];
// 读入序列
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
// 动态规划求解
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j) {
if (a[j] < a[i] && dp[j]+1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
}
// 找到最长上升子序列的长度
int max_len = 0;
for (int i = 1; i <= n; ++i) {
if (dp[i] > max_len) max_len = dp[i];
}
// 输出结果
printf("%d\n", max_len);
return 0;
}
7-6 上升子序列
一个只包含非负整数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列{a1, a2, ...,aN}，我们可以得到一些上升的子序列{ai1, ai2, ..., aiK}，这里1 ≤ i1 < i2 <...< iK ≤ N。例如：对于序列{1, 7, 3, 5, 9, 4, 8}，有它的一些上升子序列，如{1, 7}, {3, 4, 8}等等。这些子序列中序列和最大的是子序列{1, 3, 5, 9}，它的所有元素的和为18。
对于给定的一个序列，求出它的最大的上升子序列的和。
注意：最长的上升子序列的和不一定是最大的哦。
输入格式:
输入包含多组测试数据，对于每组测试数据：
输入数据的第一行为序列的长度 n(1 ≤ n ≤ 1000)，
第二行为ｎ个非负整数 b1，b2，...，bn(0 ≤ bi ≤ 1000)。
输出格式:
对于每组测试数据，输出其最大上升子序列的和。
输入样例:
7
1 7 3 5 9 4 8
输出样例:
在这里给出相应的输出。例如：
18
#include<stdio.h>
#include<string.h>
#define MAX_N 1005
int dp[MAX_N]; // dp[i] 表示以第 i 个数结尾的最大上升子序列的和
int main() {
int n, a[MAX_N];
while(scanf("%d", &n) != EOF) {
// 初始化
memset(dp, 0, sizeof(dp));
int max_sum = 0;
// 读入序列
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
// 动态规划求解
for (int i = 0; i < n; ++i) {
dp[i] = a[i]; // 初始化 dp[i] 为 a[i]
for (int j = 0; j < i; ++j) {
if (a[j] < a[i] && dp[j] + a[i] > dp[i]) {
dp[i] = dp[j] + a[i];
}
}
// 更新 max_sum
if (dp[i] > max_sum) max_sum = dp[i];
}
// 输出结果
printf("%d\n", max_sum);
}
return 0;
}
7-7 递归的函数
给定一个函数 f(a, b, c)：
如果 a ≤ 0 或 b ≤ 0 或 c ≤ 0 返回值为 1；
如果 a > 20 或 b > 20 或 c > 20 返回值为 f(20, 20, 20)；
如果 a < b 并且 b < c 返回 f(a, b, c−1) + f(a, b−1, c−1) − f(a, b−1, c)；
其它情况返回 f(a−1, b, c) + f(a−1, b−1, c) + f(a−1, b, c−1) − f(a-1, b-1, c-1)。
看起来简单的一个函数？你能做对吗？
输入格式:
输入包含多组测试数据，对于每组测试数据：
输入只有一行为 3 个整数a, b, c(a, b, c < 30)。
输出格式:
对于每组测试数据，输出函数的计算结果。
输入样例:
1 1 1
2 2 2
输出样例:
2
4
#include <stdio.h>
int f(int a, int b, int c)
{
if (a <= 0 || b <= 0 || c <= 0) {
return 1;
} else if (a > 20 || b > 20 || c > 20) {
return f(20, 20, 20);
} else if (a < b && b < c) {
return f(a, b, c - 1) + f(a, b - 1, c - 1) - f(a, b - 1, c);
} else {
return f(a - 1, b, c) + f(a - 1, b - 1, c) + f(a - 1, b, c - 1) - f(a - 1, b - 1, c - 1);
}
}
int main()
{
int a, b, c;
while (scanf("%d%d%d", &a, &b, &c) == 3) {
printf("%d\n", f(a, b, c));
}
return 0;
}
7-8 走迷宫
有一个mn格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，输入这mn个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-1表示无路）。
输入格式:
第一行是两个数m，n（1< m, n< 15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
输出格式:
所有可行的路径，输出时按照左上右下的顺序。描述一个点时用（x，y）的形式，除开始点外，其他的都要用“->”表示。如果没有一条可行的路则输出-1。
输入样例:
在这里给出一组输入。例如：
5 4
1 1 0 0
1 1 1 1
0 1 1 0
1 1 0 1
1 1 1 1
1 1
5 4
输出样例:
在这里给出相应的输出。例如：
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)
(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)
#include<stdio.h>
#include<string.h>
int s[20][20];//模拟地图
int a[1000][1000];// 记录这个点是否被走过
struct node
{
int x;
int y;
}p[1007]; //记录从起点到终点走的方案，也是用来输出的
int n,m,k,flag;
int enx,eny;
int next[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; //左上右下的顺序
void move(int x1,int y1,int k) //k是用来记录几步的，也是方便下面用循环输出
{
p[k].x=x1; //坐标 x ,因为经过下面if的判断，来到这里的点都是符合要求的
p[k].y=y1; //坐标 y ，
if(x1==enx&&y1==eny) //走到终点
{
flag=1; //声明有走到终点的路线
for(int q=0;q<=k;q++)
{ //把记录的都输出，把记录的连起来输出，就是一个路线
if(q==0)
{
printf("(%d,%d)",p[q].x,p[q].y);
}
else printf("->(%d,%d)",p[q].x,p[q].y);
}
printf("\n");
return;
}
//类似于穷举，或者平行宇宙，走一步后，又会出现4个方向可走，依次如此
for(int h=0;h<4;h++)
//试试所有的方向，按照题目的要求的顺序来碰壁，因为有四个方向，所以h<4
{
int nx=next[h][0]+x1;//开始加数进行位移，按照左上右下来位移
int ny=next[h][1]+y1;
if(nx>0&&ny>0&&nx<=n&&ny<=m&&s[nx][ny]==1&&a[nx][ny]==0)
{
//只要走的坐标位置不超过地图范围，且没走过，且在迷宫上是1就可以执行
a[nx][ny]=1;//标记此点已经走过
move(nx,ny,k+1);//递归一次说明走了一步就加一，因为是在k的基础上加1，函数结束时，回溯后，还是恢复原来的值。
//如果是用自加就在下面搭配个自减就行
a[nx][ny]=0;//回溯 ，
}
}
return;
}
int main()
{
int x,y;
while(~scanf("%d %d",&n,&m)) //多组输入
{
memset(s,0,sizeof(s)); //涉及多组输出要进行初始化
memset(a,0,sizeof(a));
memset(p,0,sizeof(p));
for(int i=1;i<=n;i++) //写迷宫地图
{
for(int j=1;j<=m;j++)
{
scanf("%d",&s[i][j]);
}
}
scanf("%d%d",&x,&y); //写入始点和终点
scanf("%d%d",&enx,&eny);
a[x][y]=1; //起点标记为1，因为一上来就在这个点
move(x,y,0);//从起点开始走
if(flag==0)
{
printf("-1\n");//如果是0说明一条路径都没有
}
}
return 0;
}
7-9 取数字问题
给定M×N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角(1,1)走到右下角(M,N)，每一步只能够向右或者向下，并且不能够走出矩阵的范围。你所经过的方格里面的数字都必须被选取，请找出一条最合适的道路，使得在路上被选取的数字之和是尽可能小的正整数。
输入格式:
输入第1行是两个整数M和N,(2<=M<=10,2<=N<=10)，分别表示矩阵的行和列的数目。接下来M行，每行包括N个整数，就是矩阵中的每一行的N个元素。
输出格式:
输出只有一行，就是一个整数，表示所选道路上数字之和所能达到的最小正整数。如果不能达到任何正整数，输出-1。
输入样例:
2 2
0 2
1 0
输出样例:
1
#include <stdio.h>
#include <string.h>
#define MAXNM 14
#define oo 123456789
int a[MAXNM][MAXNM], ans;
int m, n;
void search(int i, int j, int sum)
{
sum += a[i][j];
if(i < m)
search(i+1, j, sum);
if(j < n)
search(i, j+1, sum);
if(i == m && j == n && sum < ans && sum > 0)
{
ans = sum;
}
}
int main()
{
int i, j, sum;
scanf("%d %d", &m, &n);
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
ans = oo;
sum = 0;
search(1, 1, sum);
if(ans != oo)
printf("%d\n", ans);
else
printf("-1\n");
return 0;
}
7-10 免费馅饼
都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：
为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中期中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）
输入格式:
输入数据有多组。每组数据的第一行为以正整数n(0 < n < 100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0 <= T < 100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。
输出格式:
每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。
输入样例:
6
5 1
4 1
6 1
7 2
7 2
8 3
0
输出样例:
4
#include<stdio.h>
#include<string.h>
int dp[12][100005];
int pos,time;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n;
int a;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
{
break;
}
int i,j;
int ma=0;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
scanf("%d%d",&pos,&time);
dp[pos][time]++;
ma=max(time,ma);
}
for(i=ma-1;i>=0;i--)
{
dp[0][i]+=max(dp[0][i+1],dp[1][i+1]);
dp[10][i]+=max(dp[9][i+1],dp[10][i+1]);
for(j=1;j<10;j++)
{
dp[j][i]+=max(max(dp[j-1][i+1],dp[j][i+1]),dp[j+1][i+1]);
}
}
printf("%d\n",dp[5][0]);
}
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
29
0- 0
已为社区贡献6条内容
所有评论(0)