C语言刷题之动态规划进阶(二)

爱被打了一巴掌 2024-03-30 10:55 68阅读 0赞

**目录**

1.前言

2.最大子矩阵

1.题目

2.初步分析

3.代码实现

3.龙与地下城游戏问题

1.题目

2.初步分析

3.代码实现

4.过河

1.题目

2.初步分析

3.代码实现

--------------------

### 1.前言 ###

读者们好，经过了前面四期的训练，相信已经对一些基本的动态规划题目得心应手。本期就是动态规划刷题篇的最后一篇了，事不宜迟，我们来看今天的题目吧！

本期我们按照惯例依旧带来三道动态规划进阶例题，如下：

> 这几道题目分别是：最大子矩阵，龙与地下城游戏问题，过河

### 2.最大子矩阵 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 \* 1)子矩阵。 比如，如下4 \* 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。
> 
> #### 输入描述： ####
> 
> 输入是一个N \* N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。 已知矩阵中整数的范围都在\[-127, 127\]。
> 
> #### 输出描述： ####
> 
> 输出最大子矩阵的大小。

--------------------

#### 2.初步分析 ####

我们知道，一个子矩阵是连续的，因此这道题我们可以把问题抽象成求多个一维数组的最大连续子序列和。例如，对于第一行，我们可以看作1+2，1+2+3...，对于第二行我们可以看作2+3，2+3+4...,将这些行的组合横向相加，即可将二维数组进行优化。如，我们要求第2行到第4行之间的最大和子矩阵，我们就可以分别通过求2，2+3，2+3+4，3，3+4，4这六个一维数组的最大连续子序列和，然后比较最大值，即可得出答案。

> **我的思路是**：由于我们要求n行数组的最大子矩阵，所以我们可以先建立一个dp数组，这个数组有n行n列，每个元素代表包含矩阵第i行第j列元素的最大子矩阵和。然后建立一个辅助数组sum\[n\]代表存储数组优化后得到的和，由此我们可以得到从第j行到第k行的状态转移方程dp\[j\]\[k\]=max(dp\[j\]\[k-1\] + sum\[k\], sum\[k\])，然后每轮比较结束后求出dp数组的最大值即可求出答案。时间复杂度为O(n^3)

--------------------

#### 3.代码实现 ####

#include<stdio.h>
    #include<stdlib.h>
    int Max(int x, int y)
    {
    	return x > y ? x : y;
    }
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int** arr= (int**)malloc(sizeof(int*) * n);      //输入矩阵
    	int* sum = (int*)malloc(sizeof(int) * n);        //辅助数组
    	int** dp = (int**)malloc(sizeof(int*) * n);      //存储包含当前项元素的最大子矩阵和
    	for (int i = 0; i < n; i++)
    	{
    		arr[i]=(int*)malloc(sizeof(int) * n);
    		dp[i] = (int*)malloc(sizeof(int) * n);
    		for (int j = 0; j < n; j++)
    		{
    			scanf("%d", &arr[i][j]);
    		}
    		dp[i][0] = arr[i][0];                    //初始化dp数组
    	}
    	int ans = -32767;                            //存储最终答案，初始化值为最小值
    	for (int i = 0; i < n; i++)                  //1,1+2，...,2,2+3,...,3,3+4依次优化矩阵
    	{
    		for (int j = 0; j < n; j++)              //清空辅助数组
    		{
    			sum[j] = 0;
    		}
    		for (int j = i; j < n; j++)              //1,1+2，...,2,2+3,...,3,3+4依次优化矩阵
    		{
    			for (int k= 0; k < n; k++)          //遍历优化后的一维数组，即原二维数组每一列
    			{
    				sum[k] += arr[j][k];             //使得sum[k]即为第k列的i-j行相加结果
    				if (k == 0)
    				{
    					dp[j][k] = sum [k];
    				}
    				else if (k > 0)
    				{
    					dp[j][k] = Max(dp[j][k - 1] + sum[k], sum[k]); //优化后数组进行动态规划
    				}
    				ans = Max(ans, dp[j][k]);                      //记录本轮的最大子矩阵和
    			}
    		}
    	}
    	printf("%d", ans);
    	return 0;
    }

### 3.龙与地下城游戏问题 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 给定一个二维数组map，含义是一张地图,如以下矩阵
> 
> 游戏的规则如下:  
> 1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。  
> 2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。  
> 3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?
> 
> 根据map,输出初始血量。  
> 
> 
> #### 输入描述： ####
> 
> 第一行两个正整数n，m (1≤n,m≤10^3)，接下来n行，每行m个整数，代表mapij ,(−10^3≤mapij≤10^3)。
> 
> #### 输出描述： ####
> 
> 输出一个整数，表示答案。

![a52760583e244ee1a5de60560aabe1f4.png][] 求得骑士需要7点初始血量才能见到公主。

--------------------

#### 2.初步分析 ####

这题和之前做过的求矩阵最小路径和有异曲同工之妙。不同在于，骑士每走一格血量都不能见底。如果我们用求矩阵最小路径一样的解法，当路线上出现血瓶时，我们算出来的最小血量往往是错误的。所以需要调整状态转移方程，增加限制条件。有两种思路：从前往后和从后往前

> **我的思路是：**如果我们使用从前往后的思路，经过分析，不可避免的需要建立两个数组，一个是dp数组，存储从第一格到当前格所需最少血量，另一个数组则存储骑士到当前格时的血量，然后进行分析寻找关系。显然较复杂。所以我的想法是从后往前推，dp数组代表当前格到最后一格所需的最少血量。我们起初先默认骑士见到公主时血量为最低1，保证所求的值都为最少血量。然后我们分析得知当min(dp\[i+1\]\[j\],dp\[j+1\]\[i\])-arr\[i\]\[j\]>0时，即骑士如果只剩1血触发当前格事件后无法到达终点，因此dp\[i\]\[j\]=min(dp\[i+1\]\[j\],dp\[j+1\]\[i\])-arr\[i\]\[j\]；如果min(dp\[i+1\]\[j\],dp\[j+1\]\[i\])-arr\[i\]\[j\]<=0，即骑士如果只剩1血触发当前格事件后可以到达终点，此时令dp\[i\]\[j\]=1，为最低血量1。由以上状态转移方程我们就可以向上推得dp\[0\]\[0\]，即为所求答案

--------------------

#### 3.代码实现 ####

#include<stdio.h>
    #include<stdlib.h>
    int min(int x,int y)
    {
    	return x < y ? x : y;
    }
    int main()
    {
    	int m = 0, n = 0;
    	scanf("%d%d", &m, &n);
    	int** arr = (int**)malloc(n * sizeof(int*));
    	int** dp = (int**)malloc(n * sizeof(int*));
    	for (int i = 0; i < n; i++)                //创建数组和dp数组
    	{
    		arr[i] = (int*)malloc(m * sizeof(int));
    		dp[i] = (int*)malloc(m * sizeof(int));
    		for (int j = 0; j < m; j++)
    		{
    			scanf("%d", &arr[i][j]);
    		}
    	}
    	if (arr[n - 1][m-1] > 0)                           //给dp数组赋初值，血瓶则赋值为1，使得最小
    	{
    		dp[n - 1][m - 1] = 1;
    	}
    	else                                               //怪物则赋值使高1滴血
    	{
    		dp[n - 1][m - 1] = -arr[n - 1][m - 1] + 1;
    	}
    	for (int i = m-2; i >= 0; i--)                      //初始化最后一行
    	{
    		if (dp[n - 1][i + 1] - arr[n - 1][i] > 0)
    		{
    			dp[n - 1][i] = dp[n - 1][i + 1] - arr[n - 1][i];
    		}
    		else
    		{
    			dp[n - 1][i] = 1;
    		}
    	}
    	for (int i = n - 2; i >= 0; i--)                    //初始化最后一列
    	{
    		if (dp[i+1][m-1] - arr[i][m-1] > 0)
    		{
    			dp[i][m-1] = dp[i+1][m-1] - arr[i][m-1];
    		}
    		else
    		{
    			dp[i][m-1] = 1;
    		}
    	}
    	for (int i = n - 2; i >= 0; i--)                    //遍历求dp数组
    	{
    		for (int j = m - 2; j >= 0; j--)
    		{
    			int Min= min(dp[i][j + 1], dp[i + 1][j]);   //找出走到下一格且能走到终点所需最小 
                                                            //血量
    			if (Min - arr[i][j] > 0)                    //这个血量比当前事件大
    			{
    				dp[i][j] = Min - arr[i][j];            //当前格到终点所需最低血量即为差值
    			}
    			else                                       //比当前事件小
    			{
    				dp[i][j] = 1;                          //置1
    			}
    		}
    	}
    	printf("%d", dp[0][0]);
        free(arr);
        free(dp);
    	return 0;
    }

### 4.过河 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
> 
> 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
> 
> 数据范围：1≤L≤10^9 ，1≤S≤T≤10 ，1≤M≤100
> 
> #### 输入描述： ####
> 
> 第一行有一个正整数L ，表示独木桥的长度。
> 
> 第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数
> 
> 第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。
> 
> 所有相邻的整数之间用一个空格隔开。
> 
> #### 输出描述： ####
> 
> 只包括一个整数，表示青蛙过河最少需要踩到的石子数（青蛙可以跳水）。

--------------------

#### 2.初步分析 ####

本题如果直接进行枚举的话，也就是定义dp\[i\]为到第i个点最少需要经过的石头数量，然后从i到L进行枚举，由于1≤L≤10^9，最后会超时，所以我们需要先对数组进行优化压缩再进行枚举。我们可以发现，石头的数量范围1≤M≤100 ，因此两个石头之间可能距离会非常的大。所以如果两个石头间的距离大于最长跳跃距离T，那我们是不是可以去掉中间几个T以压缩空间，因为中间的部分不会存在石头，并不会影响计算结果。所以我们可以直接mod上T压缩空间。最后对优化后的数组进行动态规划即可。

> **我的思路是：**定义一个数组dp，代表到桥优化后的第i个点要经过的最少石头数量。然后建立数组idx代表优化后的桥，stone存储输入的石头位置。首先先对石头的位置进行升序排序，然后求出每相邻两个石头的距离，如果距离大于T则modT+T进行优化，加上T是防止与上个点重复，然后将每个石头优化后所在位置存储在idx数组中。最后对这个数组进行动态规划，状态转移方程为dp\[i\]=min(dp\[i\], dp\[i - j\] + idx\[i\])，j的取值为\[S,T\]，idx\[i\]代表当前位置是水还是石头。最后对于dp\[l\]即桥尾则比较前T个点求最小值即可得出答案。

--------------------

#### 3.代码实现 ####

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int compare(const void* a, const void* b)                 //回调函数，升序排列
    {
        return (*(int*)a) - (*(int*)b);
    }
    int min(int x,int y)
    {
        return x > y ? y : x;
    }
    int dp[2005];
    int idx[2006];
    int stone[105];
    #define inf 0x7f7f7f7f
    
    int main() {
        int L;
        int S, T, M;
        scanf("%d", &L);
        scanf("%d%d%d", &S, &T, &M);
        stone[0] = 0;                          //代表起点
        for (int i = 1; i <= M; i++) 
        {
            scanf("%d", &stone[i]);
        }
    
        //================== 去除到无意义的点位，优化压缩=============================
        qsort(stone, M+1,sizeof(int),compare);     //快速排序
        stone[M+1] = L;                           // 代表最后一个点(桥尾)
        int l = 0;                             
        for (int i = 1; i <= M+1; i++)                   //求出石头压缩优化后的点位
        {
            int dis = stone[i] - stone[i - 1];         //相邻两个石头之间的距离
            if (dis>T) 
            {
                l += dis%T+T;                                //等效于差一个T
            }
                            //等效于差dis%T
            else 
            {
                l += dis;
            }
            idx[l] = 1;                               //优化后石头位置，包括终点
        }
    
    
        // ==============枚举dp[i] 为到第i点必须跳过的最少石子数==================
    
        memset(dp, inf, sizeof(dp));   //初始化dp数组
        dp[0] = 0;                     //起点无石头
        for (int i = 1; i < l; i++)    //枚举到终点的前一个点
        {
            for (int j = S; j <= T; j++) 
            {
                if (i >= j)                       //可以从上一点跳过来
                {
                    dp[i] = min(dp[i], dp[i - j] + idx[i]);  //求出每个可以跳过来的点最小值
                }
            }
        }
    
        //===================在成功跳过去的点位里面找最小的那个===========================
        int result = 1e9;
        for (int i = 1; i <=T; i++)                //可以直接跳到终点或跳过终点的点
        {                                         
            result = min(result, dp[l - i]);      //在所有可能跳到终点的地方取最小值
        }
        printf("%d\n", result);
        return 0;
    }

--------------------

***以上，就是动态规划进阶刷题(二)的全部内容。***

***制作不易，能否点个赞再走呢qwq***

[a52760583e244ee1a5de60560aabe1f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/308bdd6501cb45509991b5537292ec7b.png