当前位置: 代码迷 >> 综合 >> SDUT PTA 动态规划
  详细解决方案

SDUT PTA 动态规划

热度:12   发布时间:2023-12-06 01:55:51.0

7-1 最长公共子序列 (20 分)

从一个给定的串中删去(不一定连续地删去)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
// 等待插入代码

7-2 走迷宫 (20 分)

有一个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<stdlib.h>
#include<string.h>
struct node
{int x, y;
}ls[400];
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int vis[16][16], mp[16][16];
int n, m, step, f, ex, ey;
void dfs(int x1, int y1){if(x1 == ex && y1 == ey){f = 1;for(int i = 0; i < step; i++){printf("(%d,%d)", ls[i].x, ls[i].y);if(i < step - 1) printf("->");}printf("\n");} else{int tx, ty;for(int i = 0; i < 4; i++){tx = x1 + dx[i]; ty = y1 + dy[i];if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[tx][ty] == 0 && mp[tx][ty] == 1){ls[step].x = tx, ls[step].y = ty;step++;vis[tx][ty] = 1;dfs(tx, ty);vis[tx][ty] = 0;// 取消标记,返回到这个点,以便寻找别的路径step--;}}}
}
int main()
{int sx, sy;scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &mp[i][j]);}}scanf("%d%d%d%d", &sx, &sy, &ex, &ey);ls[0].x = sx, ls[0].y = sy;f = 0;step = 1;vis[sx][sy] = 1;// 起始点先标记上dfs(sx, sy);if(f == 0) printf("-1\n");return 0;
}

**一个简单的dfs,倒是输出格式方面要注意。

7-3 最长上升子序列 (20 分)

一个数的序列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>
#include<stdlib.h>
// 子串:连续的n个字符  子序列:不一定连续但先后顺序一致
// 最长上升子序列不一定唯一,但长度必唯一
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
int a[1004], dp[1004];
int main()
{int N;int ans = -1;scanf("%d", &N);for(int i = 1; i <= N; i++){scanf("%d", &a[i]);dp[i] = 1;// 对每个数初始化}for(int i = 1; i <= N; i++){for(int j = 1; j < i; j++){if(a[j] < a[i]){dp[i] = max(dp[i], dp[j] + 1);// 状态转移方程}}}for(int i = 1; i <= N; i++) ans = max(ans, dp[i]); printf("%d\n", ans);return 0;
}

**dp数组储存的是从头开始到每个数最长上升子序列, 所以dp数组中最大的就是答案

7-4 取数字问题 (20 分)

给定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<stdlib.h>
int m, n;
int mp[14][14];
int ans = 0x3f3f3f3f;// 开始时先将ans置于最大
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
void dfs(int i, int j, int sum){sum += mp[i][j];if(i < m) dfs(i + 1, j, sum);if(j < n) dfs(i, j + 1, sum);if(i == m && j == n && sum > 0)// 保证答案是正整数ans = min(ans, sum);
}
int main()
{scanf("%d%d", &m, &n);for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){scanf("%d", &mp[i][j]);}}dfs(1, 1, 0);if(ans == 0x3f3f3f3f) printf("-1\n");else printf("%d\n", ans);return 0;
}

7-5 免费馅饼 (20 分)

都说天上不会掉馅饼,但有一天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<stdlib.h>
#include<string.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
int dp[100005][15];// dp[时间][坐标]
int n, x, t;
int main()
{while(~scanf("%d", &n) && n){memset(dp, 0, sizeof(dp));int maxn = -0x3f3f3f3f;// 每一组的初始化不能忘!!for(int i = 0; i < n; i++){scanf("%d%d", &x, &t);dp[t][x]++;maxn = max(maxn, t);}// 找到最大时间for(int i = maxn - 1; i >= 0; i--){// 反向存储for(int j = 0; j <= 10; j++)dp[i][j] += max(dp[i+1][j], max(dp[i+1][j-1], dp[i+1][j+1]));}// 存下三个坐标中饼最多的那个(两次比较,一次搞定)printf("%d\n", dp[0][5]);// 第一个数就是最多的馅饼个数}return 0;
}

7-6 数字三角形问题 (20 分)

给定一个由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>
#define max(a, b) (((a) > (b)) ? (a) : (b))
int a[220][220];
int maxn[220][220];
int main()
{int n;scanf("%d", &n);for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){scanf("%d", &a[i][j]);}}for(int j = 1; j <= n; j++)maxn[n][j] = a[n][j];// 最后一行的每个数先存进maxn[]for(int i = n - 1; i >= 1; i--){// 这里就要从倒数第二行开始for(int j = 1; j <= i; j++){maxn[i][j] = max(maxn[i+1][j], maxn[i+1][j+1]) + a[i][j];}// 最后一行的每个数和该数后一个数与}printf("%d\n", maxn[1][1]);return 0;
}

7-7 最长公共子序列问题 (20 分)

给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn},找出X和Y的最长公共子序列。

输入格式:

输入数据有多组,每组有两行 ,每行为一个长度不超过500的字符串(输入全是大写英文字母(A,Z)),表示序列X和Y。

输出格式:

每组输出一行,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出0。

输入样例:

ABCBDAB
BDCABA

输出样例:

4
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
char s1[501], s2[502];
int main()
{int len1, len2, dp[501][501];while(~scanf("%s%s", s1, s2)){len1 = strlen(s1);len2 = strlen(s2);for(int i = 0; i <= len1; i++)dp[i][0] = 0;for(int i = 0; i <= len2; i++)dp[0][i] = 0; for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){if(s1[i-1] == s2[j-1])dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}printf("%d\n", dp[len1][len2]);}return 0;
}

7-8 上升子序列 (20 分)

一个只包含非负整数的序列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),
第二行为n个非负整数 b1,b2,...,bn(0 ≤ bi ≤ 1000)。

输出格式:

对于每组测试数据,输出其最大上升子序列的和。

输入样例:

7
1 7 3 5 9 4 8

输出样例:

在这里给出相应的输出。例如:

18
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[1100], b[1100];
int main()
{int n;while(~scanf("%d", &n)){for(int i = 0; i < n; i++){scanf("%d", &a[i]);}b[0] = a[0];int m;for(int i = 1; i < n; i++){m = b[i] = a[i];// 第一个已经处理完了for(int j = 0; j < i; j++){if(a[j] < a[i] && b[j] + m > b[i]){// 保证:子序列上升b[i] = b[j] + m;}}}int max = -1;for(int i = 0; i < n; i++){if(b[i] > max) max = b[i];}printf("%d\n", max);}return 0;
}

7-9 递归的函数 (15 分)

给定一个函数 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>
#include<stdlib.h>
int dp[27][27][27];
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(dp[a][b][c] > 0) return dp[a][b][c];// 当还想要往下递归的时候判断一下,是否已经运算过了,运算过了直接返回就行,不用再递归。else if(a < b && b < c)return dp[a][b][c] = f(a, b, c-1) + f(a, b-1, c-1) - f(a, b-1, c);elsereturn dp[a][b][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);
}
int main()
{int a, b, c;while(~scanf("%d%d%d", &a, &b, &c)){printf("%d\n", f(a, b, c));}return 0;
}

7-10 小鑫去爬山 (20 分)

马上就要放假了,小鑫打算去爬山。
小鑫要去爬的这座山有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 a[220][220];
int maxn[220][220];
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
int main()
{int n;scanf("%d", &n);for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){scanf("%d", &a[i][j]);}}for(int j = 1; j <= n; j++)maxn[n][j] = a[n][j];// 最后一行的每个数先存进maxn[]for(int i = n - 1; i >= 1; i--){// 这里就要从倒数第二行开始for(int j = 1; j <= i; j++){maxn[i][j] = min(maxn[i+1][j], maxn[i+1][j+1]) + a[i][j];}// 最后一行的每个数和该数后一个数中最大的数}printf("%d\n", maxn[1][1]);return 0;
}