【马蹄集】第十六周——动态规划专题

这篇具有很好参考价值的文章主要介绍了【马蹄集】第十六周——动态规划专题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划专题






MT2149 最长子段和

难度:钻石    时间限制:1秒    占用内存:128M
题目描述

给出一个长度为 n n n 的序列 A A A,选出其中连续且非空的一段使得这段和最大。

格式

输入格式:第一行是一个整数,表示序列的长度 n n n
     第二行有 n n n 个整数,第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai
输出格式:输出一行一个整数表示答案。

样例 1

输入:7
   2 -4 3 -1 2 -4 3

输出:4

备注

其中: 1 ≤ n ≤ 2 e 5 ,   − 1 e 4 ≤ a i ≤ 1 e 4 1\le n\le2e5,\ -1e4\le a_i\le1e4 1n2e5, 1e4ai1e4


相关知识点:动态规划


题解


若设转移数组 dp[i] 表示 “以序号i结尾的子数列中的最大连续子段和”,则对输入的整个序列(ary[ ])而言,每个 dp[i] 的最低取值即为 ary[i]。此时,每个子序列都取第 i i i 个元素构成单元素序列。在这样的定义下,最终我们要求的就是 m a x i ∈ [ 1 , n ] d [ i ] max_{i∈[1,n]}d[i] maxi[1,n]d[i]

接下来讨论此模型的动态转移方程。由于我们每次更新 dp[i] 时,dp[i-1]都 已经存储好了 “以 i − 1 i-1 i1 结尾的最大连续子段和”,因此,dp[i] 要想取得 “以 i i i 结尾的子数列中的最大连续子段和” 就只需加上 dp[i-1] 即可。但是,加上的 dp[i-1] 必须大于0,否则这样的 “加上” 实际上会成为 “减少”。所以该模型的动态转移方程即为(其中,ary[ ]为原序列数组,i 为循环遍历指针):

if(dp[i-1] >= 0)
	dp[i] = ary[i]+dp[i-1];

注:在实际编码时,为节约内存可直接令 dp[ ]=ary[ ],则此时转移方程为:dp[i] = dp[i]+dp[i-1]。
接下来只需要遍历 dp[ ] 数组并取出其中的最大值即可。

根据这样的思路可写出以下代码(已 AC):

/*
    MT2149 最长子段和 
*/ 

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 2e5+5;
int dp[MAX];

int main( )
{
    // 录入数据 
    int n;cin>>n;
    for(int i=0;i<n;i++)
        cin>>dp[i];
    
    // 初始化结果 
    int ans = dp[0];
    
    // 状态转移
    for(int i=1;i<n;i++){
        if(dp[i-1] >= 0)
            dp[i] += dp[i-1];
        ans = max(ans, dp[i]);
    }
    
    // 输出结果
    cout<<ans<<endl; 
    
    return 0;
}

注:这道题的解法实际上非常多,还有更节约存储空间的求解方式:☞ 传送门



MT2150 旅费

难度:黄金    时间限制:1秒    占用内存:128M
题目描述

提瓦特大陆上有个贫穷的占星术士小码哥,他要从蒙德去往璃月,两个地方相隔很远,所以要搭乘车队。但是搭乘车队需要金币,而小码哥没有太多金币,幸运的是,车队在这一路上有 n n n 个停靠点,每两个停靠点之间所需要的金币数不一样,如果能选择好的话说不定能省点钱。于是小码哥找来了每个站点之间所需的路费,请你帮他找出他完成这一旅途所需要的最少的旅费。。

格式

输入格式:第一行输入一个数 n n n,表示马车中间停靠的站点数。
     接下来一个 n + 1 n+1 n+1 行的半矩阵,表示从蒙德开始,每个站点到接下来每个站点所需要的金币数。
输出格式:输出一行一个整数,表示完成这一旅途所需要的最少旅费(金币数)。

样例 1

输入:1
   6 18
   9

输出:15

备注

其中: 1 ≤ n ≤ 1000 1\le n\le1000 1n1000
任意两站间的所需旅费不超过10000。
输入数据 1 解释:
6(表示从蒙德到站点1需花费6金币)、18(表示从蒙德到璃月需花费18金币)
9(表示从站点1到璃月需花费9金币)


相关知识点: 动态规划


题解


首先对 “半矩阵” 做一个解释。对于题目输入的站点数 n n n,实际上还需要算上起始站和终点站,也就是说共有 n + 2 n+2 n+2 个站。若将这 n + 2 n+2 n+2 个站视为节点,则它们之间会有 ( n + 2 ) ( n + 1 ) 2 \frac{\left(n+2\right)\left(n+1\right)}{2} 2(n+2)(n+1) 条边(视为无向图)。因此,由这些节点构成的可达矩阵中,会形成 ( n + 2 ) ( n + 1 ) 2 \frac{\left(n+2\right)\left(n+1\right)}{2} 2(n+2)(n+1)条路段。而这些路段只占据了 ( n + 2 ) ( n + 2 ) \left(n+2\right)\left(n+2\right) (n+2)(n+2) 规格的矩阵的一半(近似),因此称 “提供了 ( n + 1 ) \left(n+1\right) (n+1) 行的半矩阵”。例如,题目给出的数据可用下图表示:

【马蹄集】第十六周——动态规划专题,MT2149 最长子段和,MT2150 旅费,MT2156 矩阵取数,MT2157 迷宫,MT21555 四柱河内塔,马蹄集试题题解,动态规划

从上图不难看出,完成这一旅途所需要的最少的旅费为 6+9=15。

对于题目给出的站点数据,我们可以将其进行编号:如蒙德→0,站点1→1,璃月→2(这样一来,对输入的站点总数 n n n ,终点站的位置始终为 n + 1 n+1 n+1)。对 “求最小旅费” 的要求,可设转移数组 dp[i] 为 “从第 i i i 个站点到终点站的最小旅费”。那么显然有 dp[n+1] = 0(终点到终点的旅费为 0),且最终待求的最小旅费为 dp[0]。同时,可知转移数组 dp[ ] 的更新方向是从后往前。

由于 dp[i] 表示 “从第i个站到终点站的最小旅费”,则在进行前向更新时,若想要 dp[i] 尽可能小,就只能在 “上一次计算得到的dp[ ]数组中,由站 i i i 到终点站的最低费用” 和 “当前站直接到中转站 j j j 的票价+上一次计算得到的由站 j j j 到终点站的最低费用” 中选更低的票价。于是可得到此题的状态转移方程为:

dp[i] = min(dp[i], ary[i][j]+dp[j])

显然,这需要枚举所有的中转情况,即要遍历上面的 “半矩阵”。例如,对以下测试数据(假设半矩阵信息被存储进数组 ary[ ][ ] 中):

【马蹄集】第十六周——动态规划专题,MT2149 最长子段和,MT2150 旅费,MT2156 矩阵取数,MT2157 迷宫,MT21555 四柱河内塔,马蹄集试题题解,动态规划

根据以上思路可写出求解该题的完整代码(已 AC):

首先置各 dp[i] 为 ary[i][n+1](即,初始直接将 “第 i i i 个站到终点站的最小旅费” 设为 “第 i i i个站直接到终点站的票价”)。于是有:

  • dp[0] = ary[0][3] = 30;
  • dp[1] = ary[1][3] = 16;
  • dp[2] = ary[2][3] = 9;
  • dp[3] = ary[3][3] = 0;

接下来逆向更新 dp[ ] 数组:

  1. i = 2(即讨论站点 2 到终点的最低旅费),当前 dp[]={30,16,9,0}。dp[ ] 数组上一次存放的从站点 2 到终点的最低旅费 dp[2] = 9。接下来向后遍历,取各个站作为中转站以尝试寻找更低的旅费组合方案。
    ① 以 j = i+1 = 3 作为中转站,此时的旅费为:ary[2][3]+dp[3] = 9+0 = 9 = dp[2],故无需更新。
    后向遍历结束,得到从站点 2出发到终点站的最低旅费为 9。
  2. i = 1(即讨论站点 1 到终点的最低旅费),当前 dp[]={30,16,9,0}。dp[ ] 数组上一次存放的从站点 1 到终点的最低旅费 dp[1] = 16。接下来向后遍历,取各个站作为中转站以尝试寻找更低的旅费组合方案。
    ① 以 j = i+1 = 2 作为中转站,此时的旅费为:ary[1][2]+dp[2] = 8+9 = 17 > dp[1],故无需更新;
    ② 以 j = i+2 = 3 作为中转站,此时的旅费为:ary[1][3]+dp[3] = 16+0 = 16 = dp[1],故无需更新。
    后向遍历结束,得到从站点 1 出发到终点站的最低旅费为 16。
  3. i = 0(即讨论从起点到终点的最低旅费),当前 dp[]={30,16,9,0}。dp[ ] 数组上一次存放的从站点 0 到终点的最低旅费 dp[0] = 30。接下来向后遍历,取各个站作为中转站以尝试寻找更低的旅费组合方案。
    ① 以 j = i+1 = 1 作为中转站,此时的旅费为:ary[0][1]+dp[1] = 6+16 = 22 < dp[1],故更新 dp[1] = 22;
    ② 以 j = i+2 = 2 作为中转站,此时的旅费为:ary[0][2]+dp[2] = 15+9 = 24 > dp[1],故无需更新;
    ③ 以 j = i+3 = 3 作为中转站,此时的旅费为:ary[0][3]+dp[3] = 30+0 = 30 > dp[1],故无需更新。
    后向遍历结束,得到从站点 0(起点)出发到终点站的最低旅费为 22。
    算法终止,最终得到 dp[ ] 数组内容为:dp[ ]={22,16,9,0}。

此外,注意到每次对某个站点的 dp[ ] 数组进行更新时,由于一开始初始化已经将 “第 i i i 个站到终点站的最小旅费” 设为 “第 i i i 个站直接到终点站的票价”,所以在后续更新时就没必要再判断 “以终点站为中转站” 时的情况,因为它初始取值就是直达终点的票价。

故此,可写出求解此题的完整代码(已 AC):

/*
    MT2150 旅费
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 1e3+5;
int ary[MAX][MAX], dp[MAX];

int main( )
{
    // 录入数据 
    int n;cin>>n;
    n++;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<=n;j++)
            cin>>ary[i][j];
        // 初始化 dp[] 数组
        dp[i] = ary[i][n];
    }
    
    // 状态转移
    for(int i=n-1;i>=0;i--)
        for(int j=i+1;j<=n;j++)
            dp[i] = min(dp[i], ary[i][j]+dp[j]);
    
    // 输出结果
    cout<<dp[0]<<endl; 
    
    return 0;
}


MT2156 矩阵取数

难度:钻石    时间限制:1秒    占用内存:128M
题目描述

给定 n × m n\times m n×m 的整数矩阵 A A A,要求每行只能选取不超过一半的元素,且总的选择元素的和要是 k k k 的倍数,求满足条件的和的最大值

格式

输入格式:第一行为 n , m , k n, m, k n,m,k
     接下来 n n n 行,为所描述的矩阵
输出格式:输出一个整数为所求答案。

样例1

输入:3 4 3
   1 2 3 4
   5 2 2 2
   7 1 1 4

输出:24

备注

所有数据均在 70 以内,且大于0。


相关知识点:动态规划


题解


这道题其实和背包问题非常相似,不过这道题的难度稍大点,因为它的维度为 2。

为便于理解这道题,下面先说明对一维情况的求解。即,现在有数组 a r y = { a 1 , a 2 , … , a m } ary=\left\{a_1,a_2,\ldots,a_m\right\} ary={a1,a2,,am} ,要求你在其中选不超过一半的数使得这些数的总和是 k k k 的倍数,且尽可能大。
待求问题的解涉及到两个参数:选了哪些数?总和对 k k k 的模?即,这两个参数的变动会对解或状态转移造成影响。但对第一个参数而言,我们更需要关注的是它选了多少个数(因为知道了序列的总长度后,可以通过循环遍历来找到最优组合,此处的最优当然是指在对 k k k 求模后得到的和尽可能大)。因此,可以设状态数组 dp[l][r] 表示 “当前从序列中选了 l l l 个数, l l l 个数的总和是 dp[l][r],dp[l][r] 对 k k k 的模为 r r r”。基于这样的设置,接下来可通过一层循环来遍历整个数组 a r y ary ary ,并在该循环内部再通过一层循环(保证所选数的个数不超过原数组元素的半数),不断尝试 “不同数量下的各种数字组合”,并将总和更大的组合方式保存下来。当整个循环结束时,dp[][] 数组的最后一行中存放的就是各种取数情况下(取数总和对 k k k 的余数)能够拿到的最大总和。即,状态转移过程为:

for(int i=1; i<m; i++)
	for(int l=m/2-1; l>=0; l++)
		for(int r=0; r<k; r++)
			dp[l+1][(r+ary[i])%k] = max(dp[l+1][(r+ary[i])%k], dp[l][r]+ary[i])

有一个细节:为什么状态转移过程中,第二重循环要从 m 2 − 1 \frac{m}{2}-1 2m1开始往前遍历呢?这其实和背包问题的要求有关。如果题目给出的对象(也就是本题中的数组元素)要求不能被重复选择,则必须逆向遍历;如果可多次选择,则需要正向遍历(对这个问题感兴趣的可以看这篇文章 ☞ 传送门)。

对于本题而言,稍微复杂的点在于,现在要从一个矩阵 a r y n × m = { a 1 , 1 , a 1 , 2 , … , a 1 , m ,   … , a n , 1 , a n , 2 , … , a n , m } ary_{n\times m}=\left\{a_{1,1},a_{1,2},\ldots,a_{1,m},\ \ldots,a_{n,1},a_{n,2},\ldots,a_{n,m}\right\} aryn×m={a1,1,a1,2,,a1,m, ,an,1,an,2,,an,m} 中选数,且对矩阵的每一行选数不能超过其列数的一半。首先,同样需要分析会影响状态转移过程的参数,很明显,依然是“选了哪些数”以及“总和对 k k k 的模”。但是,由于现在处理的数据对象是一个二维矩阵,因此在 “选了哪些数” 这个问题上,它需要两个参数:一个说明当前选了多少行,另一个说明在当前行选了多少的数。因此,可以设状态数组 dp[i][l][r] 表示 “当前已经遍历到第 i i i 行(说明前面 i − 1 i-1 i1 行已经完成了最优组合的寻找,实际上可以视该过程为记忆化搜索),并且在此行选了l个数,目前所选数的总和为 dp[i][j][r],其对 k k k 的模为 r r r”。基于这种设置,接下来可通过一个二重循环来遍历矩阵 a r y n × m ary_{n\times m} aryn×m,并在其内部采用和一维情况相似的思路进行状态转移。但是有一个不同的地方在于,状态转移过程是针对某一行的数据进行的,它的目的是求出当前这一行最优的选数组合(使得所选数对 k k k 的模在指定前提下还具有最大总和)。因此。在进行二维状态转移时,我们还需要建立每一行之间的最优值传递。即,在寻找第i行的最优取数时,需要将前面 i − 1 i-1 i1 行已经得到的结果传递过来。为此,需要在状态转移过程中的每一行的第一列进行行之间的状态转移。下面给出二维情况下的状态转移过程:

for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			// 行之间的状态转移 
			if(j == 1){
				for(int l=0;l<=m/2;l++)
					for(int r=0; r<k; r++)
						dp[i][0][r] = max(dp[i][0][r], dp[i-1][l][r]);
			}
			// 列之间的状态转移 
			for(int l=m/2-1;l>=0;l--)
				for(int r=0; r<k;r++)
					dp[i][l+1][(r+ary[i][j])%k] = max(dp[i][l+1][(r+ary[i][j])%k], dp[i][l][r]+ary[i][j]);
		}

当遍历完整个二维矩阵后,最终的结果将存放在 dp[n][0-m/2][0] 中。
下面给出基于以上思路得到的完整代码(已 AC):

/*
    MT2156 矩阵取数 
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 75;
const int INF = 0x3f3f3f3f; 
int ary[MAX][MAX], dp[MAX][MAX][MAX];

int main( )
{
    // 录入数据 
    int n, m, k, ans = -INF;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ary[i][j];
    
    // 状态数组初始化
    memset(dp, -INF, sizeof(dp));
    dp[0][0][0] = 0;
    
    // 状态转移
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            // 行之间的状态转移 
            if(j == 1){
                for(int l=0;l<=m/2;l++)
                    for(int r=0; r<k; r++)
                        dp[i][0][r] = max(dp[i][0][r], dp[i-1][l][r]);
            }
            // 列之间的状态转移 
            for(int l=m/2-1;l>=0;l--)
                for(int r=0; r<k;r++)
                    dp[i][l+1][(r+ary[i][j])%k] = max(dp[i][l+1][(r+ary[i][j])%k], 
                    dp[i][l][r]+ary[i][j]);
        }
    
    // 在最后一层寻找最大值
    for(int j=0;j<=m/2;j++)
        ans = max(ans, dp[n][j][0]);
    
    // 输出结果
    cout<<ans<<endl; 
    
    return 0;
}


MT2157 迷宫

难度:黄金    时间限制:1秒    占用内存:128M
题目描述

小码哥和他的手下在维多利亚的迷宫玩耍,小码哥并不喜欢这个项目,于是他决定以最快的速度结束这个项目,这个迷宫可以看作是一个直角坐标系,小码哥在左下,终点在右上点。
小码哥只沿 x , y x,y x,y 轴的正方向走,因为这样是理论最快的解,问小码哥有多少种行走方法来最快到达终点。

格式

输入格式:第一行两个整数 m , n m,n m,n 表示迷宫是 m m m n n n 列;
     接下来 m m m 行,每行 n n n 个数描述了地图。
     0 – 空地
     1 – 墙(无法通过)
输出格式:一个整数表示答案(mod 2333)。

样例 1

输入:3 3
   0 0 0
   0 1 0
   0 0 0

输出:2

备注

其中: m ,   n ≤ 3000 m,\ n\le3000 m, n3000


相关知识点:动态规划


题解


走迷宫问题是二维动态规划里非常经典的一类题目。考虑到表达上的习惯,我们可以对本题的任务方向进行一个改变:即现假设从二维矩阵的最左上角往最右下角走。并规定数组的索引从1开始,当方向向下和向右走时,在对应维度上的索引号增加:

【马蹄集】第十六周——动态规划专题,MT2149 最长子段和,MT2150 旅费,MT2156 矩阵取数,MT2157 迷宫,MT21555 四柱河内塔,马蹄集试题题解,动态规划

由于处理对象是二维矩阵,因此可设状态数组 dp[i][j] 表示 “走到位置 ( i , j ) \left(i,j\right) (i,j) 时共有 dp[i][j] 种行走方式”,则最终待求的就是 dp[m][n]。对任意位置 ( i , j ) \left(i,j\right) (i,j) 而言,只能由其左方 ( i , j − 1 ) \left(i,j-1\right) (i,j1) 或上方 ( i − 1 , j ) \left(i-1,j\right) (i1,j) 的位置而来。也就是说,dp[i][j] 的前一个状态只能是 dp[i][j-1] 或 dp[i-1][j]。因此,可得到本题的状态转移方程为:

dp[i][j] = dp[i][j] + (dp[i-1][j]+dp[i][j-1])

下面给出求解该题的完整代码(已 AC):

/*
    MT2157 迷宫
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 3005;
const int MOD = 2333; 
bool ary[MAX][MAX];
int dp[MAX][MAX];

int main( )
{
    // 录入数据 
    int n, m;
    cin>>m>>n;
    for(int i=m;i>=1;i--)
        for(int j=1;j<=n;j++)
            cin>>ary[i][j];
    
    // 状态数组初始化
    dp[1][1] = 1; 
    
    // 状态转移
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(!ary[i][j]){
                dp[i][j] += (dp[i-1][j]+dp[i][j-1]);
                dp[i][j] %= MOD;
            }
    
    // 输出结果
    cout<<dp[m][n]<<endl; 
    
    return 0;
}


MT2155 四柱河内塔

难度:黄金    时间限制:1秒    占用内存:128M
题目描述

汉诺塔问题:有三个柱子,编号为 1,2,3;在编号为 1 的柱子上有 n 个大小不同圆盘,圆盘从小到大,从上到下堆叠,你只可以移动一个柱子上最上面的圆盘。
现在你需要将编号为 1 的柱子上的圆盘移到 3 柱子上,顺序不变;
注意:在移动过程中,不可以将大的圆盘放在小圆盘上,你一次只可以移动一个盘子;
现在有一个 4 个柱子的河内塔,在规则不变的情况下,问最少需要移动多少次才能把盘子从 1 号柱子移到 4 号柱子上。

格式

输入格式:一个整数 f f f ,表示 n n n [ 1 ,   f ] \left[1,\ f\right] [1, f] 时的 f f f 种情况;
输出格式:输出 f f f 行,表示当 n n n 分别取 [ 1 ,   f ] \left[1,\ f\right] [1, f] 的情况下,需要的最少移动次数。

样例 1

输入:12

输出:1
   3
   5
   9
   13
   17
   25
   33
   41
   49
   65
   81

备注

其中: 1 ≤ n ≤ 50 1\le n\le50 1n50


相关知识点:动态规划


题解


我们首先来思考,经典汉诺塔问题(存在 A、B、C ,3 根柱子)的动态规划解法。
假设现在要将 n n n 个圆盘从 A 柱移动至 C 柱。显然,需要的移动次数仅仅和当前的圆盘数量 n n n 有关。故可以假设 d p [ n ] dp[n] dp[n] 表示 “移动 n n n 个圆盘到另一个柱子需要的最少移动次数”。那么将第 n n n 个圆盘从 A 柱移动至 C 柱需要以下三步:

  1. 将第 n n n 个圆盘上的 n − 1 n-1 n1 个圆盘从 A 移动至 B 柱,这一步最少需要 d p [ n − 1 ] dp[n-1] dp[n1] 次移动;
  2. 将第 n n n 个圆盘从 A 移动至 C 柱,这一步最少需要 1 次移动;
  3. 将B柱上的 n − 1 n-1 n1 个圆盘移动至 C 柱,这一步最少需要 d p [ n − 1 ] dp[n-1] dp[n1] 次移动。

显然,从上面可以得到 “将 n n n 个圆盘从 A 柱移动至 C 柱” 需要的最小移动次数为 d p [ n − 1 ] + 1 + d p [ n − 1 ] = 2 d p [ n − 1 ] + 1 dp[n-1]+1+dp[n-1]=2dp[n-1]+1 dp[n1]+1+dp[n1]=2dp[n1]+1。即得了经典汉诺塔问题的状态转移方程为: d p [ n ] = 2 d p [ n − 1 ] + 1 dp[n] = 2dp[n-1]+1 dp[n]=2dp[n1]+1。从这个公式不难看出,汉诺塔问题的最小移动次数与其圆盘总数存在以下关系:

d p [ n ] = 2 n − 1 dp\left[n\right]=2^n-1 dp[n]=2n1

现在假设存在 4 根柱子,其余要求都不变,问不同数量圆盘对应的最少移动次数。
在只有 3 根柱子时,为了将第 n n n 个圆盘移动至目标柱子(C 柱),就必须将第 n n n 个圆盘前的 n − 1 n-1 n1 个圆盘均移至除所在柱子(A 柱)和目的柱子以外的第 3 根柱子(B 柱)。因此这个状态转移过程是唯一的。而当柱子数多了 1 个后,这个过程变得不再唯一。因为我们可以将移动过程进行分解,从而大幅降低总的移动次数。例如,对于含有 n n n 个圆盘的柱子 A,我们可以通过以下步骤将其全部移至柱子 D:

  1. 将柱子 A 上的前 n − k n-k nk 个圆盘先移至柱子 B,这一步最少需要 d p [ n − k ] dp[n-k] dp[nk] 次移动;
  2. 将柱子 A 上剩下的 k k k 个圆盘通过柱子 C 再移动至柱子 D;
  3. 将柱子 B 上的前 n − k n-k nk 个圆盘移动至柱子 D,这一步最少需要 d p [ n − k ] dp[n-k] dp[nk] 次移动。

对于步骤 2,该过程实际上就是 “求具有 k k k 个圆盘的经典汉诺塔问题”。因为这一步执行时,剩下的 k k k 个圆盘都比柱子 B 上的更大,因此它们的移动过程只能用剩余 3 根柱子,即 A,C,D柱。

为什么分解后会大幅降低总的移动次数?从数学的角度看:因为 f ( x ) = 2 x f(x)=2^x f(x)=2x 是一个二阶导大于 0 的凸函数,它始终满足 f ( a + b ) ≥ f ( a ) + f ( b ) f\left(a+b\right)\geq f\left(a\right)+f\left(b\right) f(a+b)f(a)+f(b) 。因此,可通过枚举所有的 a + b a+b a+b 来寻找这里面具有最小取值的 f ( a ) + f ( b ) f\left(a\right)+f\left(b\right) f(a)+f(b)。例如, f ( 5 ) = 2 5 = 32 f(5)=2^5=32 f(5)=25=32 ,而 f ( 2 ) + f ( 3 ) = 2 2 + 2 3 = 4 + 8 = 12 f(2)+f(3)=2^2+2^3=4+8=12 f(2)+f(3)=22+23=4+8=12 ,可见,分解后确实能更大程度的降低需要移动的次数。

因此,如果假设四柱汉诺塔问题的状态数组为 D P [   ] DP[\ ] DP[ ],三柱汉诺塔问题的状态数组为 d p [   ] dp[\ ] dp[ ],则从前面的步骤可总结出四柱汉诺塔问题的状态转移方程为:

for(int j=1; j<n; j++)
DP[j] = 2DP[n-j]+dp[j];

下面给出基于以上思路的完整代码(已 AC):文章来源地址https://www.toymoban.com/news/detail-674870.html

/*
    MT2155 四柱河内塔
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 55;
const int INF = 0x3f3f3f3f; 
int dp[MAX];

int main( )
{
    int f, tmp; cin>>f;
    
    // 状态数组初始化
    memset(dp, INF, sizeof(dp));
    dp[0] = 0, dp[1] = 1, dp[2] = 3 ;
    
    if(f>=1) cout<<1<<endl;
    if(f>=2) cout<<3<<endl;
    
    // 状态转移并输出结果 
    for(int i=3;i<=f;i++){
        for(int j=1;j<i;j++){
            if(dp[i] > 2*dp[i-j] + pow(2,j) - 1)
                dp[i] = 2*dp[i-j] + pow(2,j) - 1;
        }
        // 输出结果
        cout<<dp[i]<<endl; 
    }
    
    return 0;
}

END


到了这里,关于【马蹄集】第十六周——动态规划专题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【马蹄集】—— 概率论专题:第二类斯特林数

    难度:黄金    时间限制:5秒    占用内存:128M 题目描述 输入两个矩阵,第一个矩阵尺寸为 l × m l×m l × m ,第二个矩阵尺寸为 m × n m×n m × n ,请你输出这两个矩阵相乘后的结果矩阵。 格式 输入格式:第一行输入三个整数 l , m l,m l , m 和 n n n ;       接下来 l

    2024年02月22日
    浏览(52)
  • 动态规划专题

    法一:线性DP 这题目最重要的是根据必须在(2N-1)个单位时间内穿越出去,推导出此题的解题的重要性质。 曼哈顿距离 : 两个点在标准坐标系上的绝对轴距总和,d=|x2−x1|+|y2−y1 此题虽然说可以向上下左右四个方向移动,但是根据2n-1个单位时间的限制结合曼哈顿距离,我

    2024年02月05日
    浏览(35)
  • 动态规划专题——背包问题

    🧑‍💻 文章作者:Iareges 🔗 博客主页:https://blog.csdn.net/raelum ⚠️ 转载请注明出处 本文主要介绍常见的四种背包问题,思维导图如下: 💡 现有 N N N 件物品和一个最多能承重 M M M 的背包,第 i i i 件物品的重量是 w i w_i w i ​ ,价值是 v i v_i v i ​ 。在背包能承受的范围内

    2024年02月03日
    浏览(42)
  • 第四十六章 动态规划——状态机模型

    其实状态机DP只是听起来高级,其实我们之前做的所有关于DP的题几乎都算是状态机,为什么呢? 大家继续向下看: DP解决的是多决策的问题,那么我们可以把01背包问题画成下面的图: 按照正常的逻辑,我们一般都是从第一个物品开始看,决定选或者不选,然后再去看第二

    2024年02月16日
    浏览(43)
  • 【算法专题】动态规划之路径问题

    题目链接 - Leetcode -62.不同路径 Leetcode -62.不同路径 题目:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示

    2024年01月24日
    浏览(48)
  • 【蓝桥杯C/C++】专题六:动态规划

    在这里插入图片描述 本专题将讲解 最难理解 的算法之一:动态规划。介绍动态规划的基本概念、算法原理以及应用场景。首先,我们将介绍动态规划的定义和特点,以及它与递归、贪心算法的区别。接着,我们将详细介绍动态规划的解题思路和算法流程,包括状态转移方程

    2024年02月01日
    浏览(49)
  • 【动态规划专栏】专题二:路径问题--------1.不同路径

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年02月20日
    浏览(46)
  • leetcode-打家劫舍专题系列(动态规划)

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年04月14日
    浏览(44)
  • 动态规划。第十三次

    2024.2.28 ************************************************************************************************************** 题目链接:P1002 [NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)  思路:用dfs其实也可以写,不过这道题目会超时。由于题目上说只能往右边还有下面走,所以每一点

    2024年03月14日
    浏览(29)
  • 【动态规划专栏】专题二:路径问题--------6.地下城游戏

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年02月22日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包