C++：第十四讲动态规划初步

每日C++知识

想要在做C++小游戏里实现等待效果，可以用Sleep。

Sleep函数可以使计算机程序（进程，任务或线程）进入休眠，使其在一段时间内处于非活动状态。

一般需要头文件windows.h。

注意"Sleep"首字母要大写，小括号内参数单位是毫秒。

下面这个示例程序可以帮助你了解一下这个函数：

#include <windows.h>  //需要的头文件int main(void)
{Sleep(1000);    //单位，毫秒 (在VC中Sleep中的第一个英文字符为大写的"S")}

注意

1.用万能头文件不管用了，要包含windows头文件：

#include<windows.h>
2.n可以自由更改，但不要太大，否则容易卡住。

3.Sleep函数一定要大写，否则不管用，会报错。

关于Sleep函数使用
Windows下是大写字母开头的Sleep()，单位为毫秒，linux下面是小写的sleep()。Linux下的sleep()函数是以秒为单位的，sleep(1)就是休眠1毫秒，想实现更短的休眠，linux下有usleep()函数。

记住，Sleep函数中（）内只能是数字！

前言

今天带着大家学一个较难的算法——动态规划，简称动规（dp）

动态规划简介

动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。

动态规划是一种解决复杂问题的优化策略，它通过对问题进行分而治之的技巧，特别是通过识别并利用子问题间的重叠特性，避免不必要的重复计算，从而达到高效求解的目的。具体来说，动态规划的核心思想是将原问题分解成若干个规模较小的子问题，通过求解这些子问题的最优解来间接获得原问题的最优解。这种方法不仅适用于数学优化问题。

如：

线性动规：拦截导弹、合唱队形、挖地雷、建学校、剑客决斗等；
区域动规：石子合并、加分二叉树、统计单词个数、炮兵布阵等；
树形动规：贪吃的九头龙、二分查找树、聚会的欢乐、数字三角形等；
背包动规：背包问题（easy）、完全背包问题、分组背包问题、二维背包、装箱问题、挤牛奶等；

动态规划的本质，是对问题状态的定义和状态转移方程的定义（状态以及状态之间的递推关系）。
动态规划问题一般从以下四个角度考虑：

状态定义；
状态间的转移方程定义；
状态的初始化；
返回结果；

例子1 洛谷P1020 导弹拦截

链接——【全网首发】洛谷P1020 [NOIP1999 提高组] 导弹拦截-CSDN博客

AC

//这题满分200！！！
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN=1e5+3;
int n,t,H[MAXN],F[MAXN];
int main(){while(~scanf("%d",&H[++n])); --n;t=0,memset(F,0,sizeof(F)),F[0]=INF;up(1,n,i){int l=0,r=t+1; while(r-l>1){int m=l+(r-l)/2;if(F[m]>=H[i]) l=m; else r=m;}int x=l+1;  // dp[i]if(x>t) t=x; F[x]=H[i];}printf("%d\n",t);t=0,memset(F,0,sizeof(F)),F[0]=0;up(1,n,i){int l=0,r=t+1; while(r-l>1){int m=l+(r-l)/2;if(F[m]<H[i]) l=m; else r=m;}int x=l+1;if(x>t) t=x; F[x]=H[i];}printf("%d\n",t);return 0;
}

例子2洛谷P1002 过河卒

链接——题目在这里！！！

题目描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A 点 (0,0)、B 点(n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 B 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

输入输出样例

输入 #1

6 6 3 3

输出 #1

说明/提示

对于 100% 的数据，1≤n,m≤20，0≤ 马的坐标≤20。

解题思路

矩阵乘法

由于数据很小，n 和 m 的规模只有 20，所以允许一些复杂度较大的做法通过。

如果我们给网格图内的点标号，记从 i 号点到达 j 号点的方法数为 f(i,j)，i 号点到 j 号点的边的条数为 ∈{0,1})a(i,j)(a(i,j)∈{0,1})，那么枚举经过的点 k，则有 i 点到 j 点的方法数 =i 点到k 点的方法数 ×k 点到 j 点的方法数，形式化的讲，f(i,j)=f(i,k)⋅a(k,j)。

我们惊奇的发现，这就是矩阵乘法的定义。

因此，我们连接所有互相可达的点，进行矩阵快速幂即可。

有一种特殊情况：如果起点或终点离马的位置太近，那么上面的分类讨论的第 4 种和第 5 种情况就会出现问题——可能起点或终点本来就在马的攻击范围内。

所以，遇到这种情况别忘记特判。

AC

#include<iostream>
using namespace std;
const int N = 35;
int n, m, x, y;
long long dp[N][N];   
bool vis[N][N];
int X[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int Y[8] = {-1, -2, -2, -1, 1, 2, 2, 1};  
int main()
{cin >> n >> m >> x >> y;dp[2][1] = 1;vis[x+2][y+2] = 1;for (int i = 0; i < 8; i ++)vis[x+X[i]+2][y+Y[i]+2] = 1;  for (int i = 2; i <= n+2; i ++)for (int j = 2; j <= m+2; j ++) {if (vis[i][j])continue;  dp[i][j] = dp[i-1][j] + dp[i][j-1];}cout << dp[n+2][m+2];return 0;
}

例子3洛谷P1216 数字三角形

链接——题目在这里！！！

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 7→3→8→7→5的路径产生了最大权值。

输入格式

第一个行一个正整数 r ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

输入输出样例

输入 #1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出 #1

说明/提示

【数据范围】
对于100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。

解题思路

分析题干，发现从上面往下一步步走很麻烦，直接搜索肯定超时。所以，逆向求解。

看样例分析：

        7 3   8 8   1   0 2   7   4   4 
4   5   2   6   5

若从倒数第二排的‘2’开始走，只有2个选择，往左下方和右下方。

往左下方是‘4’，得到的最终值为6，往右下方是‘5’，得到的最终值是7.这时当然选择右下方。

我们就将‘2’改写成2+5=7。再次考虑倒数第二排的7，

同理，应选择左下，得到最终值是12。还是将‘7’改写成5+7=12。

依次类推则倒数第二排变为：

7 12 10 10

原数字三角形变为：

        7 3   8 8   1   0 7   12  10  10 
4   5    2    6   5

这时再考虑第三行第一个。有两种选择：左下和右下。

假设走左下方，由于这时左下的值已经是从左下开始走到底的最优值，我们不需要在选择下一步怎么走，直接加上左下的值即可。

同理，走右下时，直接加上右下的值即可。因为此时右下的值已经是从右下走到底的最优值，不需要选择了。

再比较走两条路的值，右边的值更大，选择右边的值。则第三行的第一个值更新为8+12=20。

以此类推，得到下面的数字三角形：

        7 3   8 20  13  10 7   12  10  10 
4   5    2    6   5

同理，更新第二排，有：

           7 23   21 20   13   10 7   12   10  10 
4    5    2    6    5

最后一个了，有：

           30 23   21 20   13   10 7   12   10  10 
4    5    2    6    5

AC

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=1e5+5;
int m[1005][1005];
int dp[1005];
int main()
{ios_base::sync_with_stdio(NULL);cin.tie(NULL),cout.tie(NULL);int n;cin>>n;for(int i=0;i<n;i++)for(int j=0;j<i+1;j++)cin>>m[i][j];for(int i=0;i<n;i++)dp[i]=m[n-1][i];for(int i=n-2;i>=0;i--){for(int j=0;j<i+1;j++)dp[j]=max(m[i][j]+dp[j],m[i][j]+dp[j+1]);}cout<<dp[0]<<endl;return 0;
}

课后小练习P1049 装箱问题

链接——题目在这里！！！

题目描述

有一个箱子容量为V，同时有n 个物品，每个物品有一个体积。

现在从n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 V，表示箱子容量。

第二行共一个整数 n，表示物品总数。

接下来 n 行，每行有一个正整数，表示第 i 个物品的体积。

输出格式

共一行一个整数，表示箱子最小剩余空间。

输入输出样例

输入 #1

24
6
8
3
12
7
9
7

输出 #1

说明/提示

对于 100%数据，满足 n≤30，1≤V≤20000。

解题思路

这道题看似是搜索，但是可以用背包做。

题目要求求出最小的剩余空间，也就是要求出最大的可装重量

这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的01背包问题：

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）和一个价值（等于体积）。

要求n个物品中，任取若干个装入箱内，使总价值最大。

对于每一个物体，都有两种状态：装与不装

那么，对于任意重量m的最大价值 f (m) = max ( f ( m - w[i] ) + w[i], f (m) )（w为重量（即价值））

其中，f ( m - w[i] ) 指在装了物品i后，箱子的剩余容量能装的最大重量

f ( m - w[i] ) + w[i] 指在在装了物品i后，箱子能装的最大重量

AC

#include<bits/stdc++.h>
using namespace std;
bool b[20005];
int n, v;
int a[35];
int main(){cin >> v >> n;for (int i = 1; i <= n; i++) cin >> a[i];b[0] = 1;for (int i = 1; i <= n; i++)  for (int j = v; j >= a[i]; j--)if (b[j - a[i]]) b[j] = 1;for (int i = v; i >= 1; i--)if (b[i]){cout << v - i;break;}	return 0;
}

思考题洛谷P1091 合唱队形

链接——题目在这里！！！

解题思路

本人觉得这题是很不错的，虽然难度不高。首先，我们要想出列最少，那么就想要留下的最多。很容易想的最长升，但是，这个序列是一个中间高，两头底的序列，最长升只能处理出单调性的序列。我们先看从T1到Ti这一段单调递增的序列，再看Ti到TK这一段单调递减的序列，那么问题就解决了。先从1到n求一趟最长升，然后从n到1也求一趟，最后枚举中间的Ti，然后从众多Ti中挑个大的。

AC

#include<iostream>
#include<cstdio>
using namespace std;
int g[105],f[105],a[105],s[105];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];f[i]=1;g[i]=1;}for(int i=n-1;i>=1;i--){for(int j=i+1;j<=n;j++){if(a[i]>a[j]&&f[i]<=f[j]+1){f[i]=f[j]+1;}}}for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(a[i]>a[j]&&g[i]<=g[j]+1){g[i]=g[j]+1;}}}int maxx=0;for(int i=1;i<=n;i++){s[i]=f[i]+g[i]-1;if(s[i]>maxx){maxx=s[i];}}cout<<n-maxx;
}