SDUT-程序设计基础Ⅱ-实验六-动态规划

1-1 最长公共子序列

任务描述:

从一个给定的串中删去(不一定连续地删去)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

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
#include 
char a[110][110];
int d[30010];
int len[110];
int n;
int f(int *x)
{
    int i,j,index,ret,t;
    for(i=1;i<=n;i++) { if(x[i]==0) { return 0; } } for(index=x[n]-1,i=n-1;i>=1;i--)
    {
        index=index*len[i]+x[i]-1;
    }
    if(d[index]>=0)
    {
        return d[index];
    }
    for(i=2;i<=n;i++) { if(a[1][x[1]-1]!=a[i][x[i]-1]) { break; } } if(i>n)
    {
        for(j=1;j<=n;j++)
        {
            x[j]--;
        }
        ret=f(x)+1;
        for(j=1;j<=n;j++)
        {
            x[j]++;
        }
    }
    else
    {
        ret=0;
        for(j=1;j<=n;j++) { x[j]--; t=f(x); if(t>ret)
            {
                ret=t;
            }
            x[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;
}

1-2 走迷宫

任务描述:

有一个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)

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
#include 
int a[30][30];
int b[100];
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int c,d,f;
void s(int g,int h,int k)
{
    int i;
    if(g==c&&h==d)
    {
        f=1;
        for(i=0;i<k;i+=2)
        {
            printf("(%d,%d)",b[i],b[i+1]);
            if(i<k) printf("->");
        }
        printf("(%d,%d)\n",c,d);
        return;
    }
    if(!a[g][h])
    return;
    for(i=0;i<4;i++)
    {
        a[g][h]=0;
        b[k]=g;
        b[k+1]=h;
        s(g+dir[i][0],h+dir[i][1],k+2);
        a[g][h]=1;
    }
}
int main()
{
    int n,m,g,h,i,j,k;
    while(~scanf("%d %d",&n,&m))
    {
        k=f=0;
        memset(b,0,sizeof(b));
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
        {
           for(j=1;j<=m;j++)
            {
              scanf("%d",&a[i][j]);
            }
        }
        scanf("%d %d %d %d",&g,&h,&c,&d);
        s(g,h,0);
        if(!f)
        printf("-1\n");
    }
    return 0;
}

1-3 最长上升子序列

任务描述:

一个数的序列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

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int main()
{
	int n,i,j;
	scanf("%d",&n);
	int list[n],max[n];  
	for( i = 0; i < n; ++i)
	{
		scanf("%d",&list[i]);
		max[i]=1;
	}
	for( i = 1; i < n; ++i)
		for( j = 0; j < i; ++j)                   
		{					    
			if(list[j]<list[i] && max[j]>=max[i])
			{				     
				max[i] = max[j] + 1;         
			}				     
		}
	 j = -1;
	for( i = 0; i < n; ++i)
           { 
             if(max[i]>j)
             j = max[i];
	   }
	printf("%d\n",j);
	return 0;
}

1-4 取数字问题

任务描述:

给定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

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int max=10000000;
int a[30][30],n,m;
void f(int i,int j,int sum);
int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    f(1,1,0);
    if(max==10000000)
    {
        max=-1;
    }
    printf("%d\n",max);
    return 0;
}
void f(int i,int j,int sum)
{
    sum+=a[i][j];
    if(i<n)
    {
        f(i+1,j,sum);
    }
    if(j<m)
    {
        f(i,j+1,sum);
    }
    if(i==n&&j==m&&sum<max&&sum>0)
    {
        max=sum;
    }
}

1-5 免费馅饼

任务描述:

都说天上不会掉馅饼,但有一天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

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int a[100003][13];
int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int main()
{
    int n,i,j,t,x,ma;
    while(scanf("%d",&n)!=EOF&&n)
    {
        ma=0;
        memset(a,0,sizeof(a));
        scanf("%d %d",&x,&t);
        ma=t;
        a[t][x]++;
        for(i=2; i<=n; i++) { scanf("%d %d",&x,&t); a[t][x]++; if(t>ma) ma=t;
        }
        for(i=ma-1; i>=0; i--)
        {
            for(j=0; j<=10; j++)
            {
                if(j==0)
                  a[i][j]=max(a[i+1][j],a[i+1][j+1])+a[i][j];
                else if(j==10)
                  a[i][j]=max(a[i+1][j],a[i+1][j-1])+a[i][j];
                else
                   a[i][j]=max(a[i+1][j-1],max(a[i+1][j],a[i+1][j+1]))+a[i][j];
            }
        }
        printf("%d\n",a[0][5]);}
    return 0;
    }

1-6 数字三角形问题

任务描述:

给定一个由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

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int main()
{
    int a[105][105],d[105][105],n,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            scanf("%d",&d[i][j]);
        }
    }
    for(i=1;i<=n;i++) { a[n][i]=d[n][i]; } 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;
}

1-7 最长公共子序列问题

任务描述:

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

输入格式:

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

输出格式:

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

输入样例:

在这里给出一组输入。例如:

ABCBDAB
BDCABA

输出样例:

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

4

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
#include
int a[501][501];
int max(int a,int b);
int main()
{
    char x[501];
    char y[501];
    int n,m,i,j;
    while(~scanf("%s %s",x,y))
    {
        n=strlen(x);
        m=strlen(y);
        for(i=0;i<n;i++)
            a[i][0]=0;
        for(j=0;j<m;j++)
            a[0][j]=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++) { if(x[i-1]==y[j-1]) { a[i][j]=a[i-1][j-1]+1; } else { a[i][j]=max(a[i-1][j],a[i][j-1]); } } } printf("%d\n",a[n][m]); } return 0; } int max(int a,int b) { return a>=b?a:b;
}

1-8 上升子序列

任务描述:

一个只包含非负整数的序列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

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int main()
{
    int n,a[1010],i,k,M[1010],m,nmax;
    while(~scanf("%d",&n))
    {for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    M[1]=a[1];
    for(k=2;k<=n;k++)
    {
  m=0;
        for(i=1;i<k;i++) { if(a[k]>a[i]&&M[i]>m)
            {
                m=M[i];
            }
        }
        M[k]=a[i]+m;
    }
    nmax=-1;
    for(i=1;i<=n;i++) { if(M[i]>nmax)
            nmax=M[i];
    }
    printf("%d\n",nmax);}
}

1-9 递归的函数

任务描述:

给定一个函数 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

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int p[21][21][21]={0};
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)
    {
        if(p[20][20][20]==0)
            p[20][20][20]=f(20,20,20);
        return p[20][20][20];
    }
    else if(a<b&&b<c)
    {
        if(p[a][b][c]==0)
            p[a][b][c]=f(a,b,c-1)+f(a,b-1,c-1)-f(a,b-1,c);
        return p[a][b][c];
    }
    else
    {
        if(p[a][b][c]==0)
            p[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);
        return p[a][b][c];
    }
}
int main()
{
    int a,b,c;
    while(~scanf("%d %d %d",&a,&b,&c))
        printf("%d\n",f(a,b,c));
    return 0;
}

1-10 商人的诀窍

任务描述:

马上就要放假了,小鑫打算去爬山。小鑫要去爬的这座山有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

相关限制:

代码长度限制16KB            时间限制1000ms            内存限制64MB            栈限制8192KB

答案:

#include <stdio.h>
int main ()
{
    int a[105][105];
    int n,i,j;
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<i+1;j++) { scanf("%d",&a[i][j]); } } int b[105][105]; for(i=n-1;i>=0;i--)
        {
            for(j=0;j<i+1;j++)
            {
                if(i==n-1)
                    b[i][j]=a[i][j];
                else
                {
                    b[i][j]=a[i][j];
                    if((b[i+1][j]+b[i][j])<=(b[i+1][j+1]+b[i][j]))
                        b[i][j]=b[i+1][j]+b[i][j];
                    else
                        b[i][j]=b[i+1][j+1]+b[i][j];
                }
            }
        }
        printf("%d\n",b[0][0]);
    }
    return 0;
}
如果对您有帮助的话,能否支持一下博主?
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇