- 1Selenium元素定位方法：class_name定位_selenium class_name
- 2【Rust日报】2020-07-16 j4rs，一个在 Rust 中调用 Java 代码的 Crate
- 3RPA的基本概念，RPA介绍及作用，RPA是干什么的_通俗介绍rpa
- 4程序员笔试题收集汇总（三）_中等程序员笔试题
- 5解决：pip is configured with locations that require TLS/SSL, howeve......_linux warning: pip is configured with locations th
- 6rustc cargo Rust 版本 Cargo 更改源_rustc 版本
- 7pytorch中模型训练的学习率动态调整
- 8阿里云：访问公网IP地址需要在实例安全组白名单中增加Workbench的服务器白名单_访问公网ip地址需要在实例安全组白名单中增加 workbench的服务器白名单
- 9VC++六种Runtime Library
- 10Github Actions实现CI/CD（golang项目）
动态规划笔记+经典习题十道_算法导论动态归回练习题
赞
踩
《算法导论》笔记
（1）动态规划与贪心算法导论
动态规划通常应用于最优化问题，即要做出一组选择以达到一个最优解。在做选择的同时，经常出现同样形式的子问题。当某一特定的子问题可能出自于多于一种选择的集合时，动态规划是很有效的；关键技术是存储每一个子问题的解，以备它重复出现。利用这种简单思想，可将时间复杂度从指数级别降低到多项式级别。
贪心算法通常也是应用于最优化问题。在这种算法中，要做出一组选择以达到一个最优解。该算法的思想是以局部最优的方式来做每一个选择。对许多问题来说，采用贪心法可以比动态规划更快地给出一个最优解。但是，不容易判断贪心法的正确性。可用回顾拟阵理论进行判断。
贪心算法与动态规划有一个显著的区别，在于使用最优子结构的顺序，前者是自顶向下。贪心算法会先做选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先寻找子问题的最优解，然后再做选择。
（2）动态规划导论
动态规划是通过组合子问题的解而解决整个问题的。动态规划适用于子问题不是独立的情况，即各子问题包含公共的子子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免重复计算子问题。
动态规划通常应用于最优化问题。此类问题可能有很多种可行解。每个解有一个值，而我们希望找出一个具有最优（最大或最小）值的解。称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优值的解。
算法设计步骤：
1）描述最优解的结构。
以正序扩展可见区域，考虑从起点到区域边界的最优解。
定义问题，假设其包含了子问题并加以证明。
定义子问题，利用子问题的最优解来构造原问题的一个最优解。
2）递归定义最优解的值。
列出包含边界情况的递归公式（形式类似于分段函数）
3）按自底向上的方式计算最优解的值。
方向由递归公式确定。
4）由计算出的结果构造一个最优解。
第1~3步构成问题的动态规划解的基础。第4步在只要求计算最优解的值时可以略去。如果的确做了第4步，则有时要在第3步的计算中记录一些附加信息，使构造一个最优解变得容易。
（3）动态规划基础
适合采用动态规划方法的最优化问题的两个要素：最优子结构和重叠子问题。注意子问题要互相独立，即不共享资源。
（4）最优子结构
如果一个问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。在这种情况下，贪心也可能适用。
寻找时遵循的模式：
1）问题的一个解可以是做一个选择，做这种选择会得到一个或多个有待解决的子问题。
2）假设对一个给定的问题，已知一个可以得出最优解的选择，不必关心如何确定这个选择。
3）在已知这个选择之后，确定哪些子问题会随之产生，以及如何最好地描述所得到的子问题空间。规则是，尽量保持这个空间简单，然后在需要时再扩充它，在合适的情况下没有必要再去尝试一个更具一般性的子问题空间。
4）利用“剪贴”技巧来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。假设子问题的解不是最优，通过“剪除”非最优解再“贴上”最优解，就证明了可以得到原问题的一个更好的解，因此，这与得到的是最优解的假设矛盾。
最优子结构在问题域中以两种方式变化：
1）要在多少种选择中选出最优。
2）每种选择使用的子问题数量。
动态规划以自底向上的方式来利用最优子结构。也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。
（5）重叠子问题
当一个递归算法不断地调用同一问题时，称该最优问题包含重叠子问题。子问题的空间要“很小”，也就是用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。动态规划使用表格把时间复杂度从指数级别降低到多项式级别。
HDOJ-2084 数塔
题目
有一个形如金字塔的数塔，从顶层走到底层，若每一步只能走到相邻的结点，求经过的结点的数字之和的最大值。
思路
最优子结构： 该问题（找出从顶点出发的最大路线）的最优解包含了子问题（找出从与顶点相邻的点出发的最大路线）的一个最优解。
利用子问题的最优解来构造原问题的一个最优解： 从顶点出发的路线必定经过从与顶点相邻的点。因此，经过顶点的最大路线只能是二者之一：从顶点出发走到点（2，1），走从点（2，1）出发的最大路线；从顶点出发走到点（2，2），走从点（2，2）出发的最大路线。
递归定义最优解的值： 选择从（i,j）出发的最大路线的问题作为子问题，层编号i=1,2,…,n。第i层的列编号j=1,2,…,i。令t[i][j]表示从点(i,j)出发可能得到的最大值。
我们的最终目标是确定从(1,1)出发得到的最大值。当i==n时，路线仅包含自身的点。递归公式：
t
[
i
]
[
j
]
=
{
t
[
i
]
[
j
]
+
m
a
x
(
t
[
i
+
1
]
[
j
]
,
t
[
i
+
1
]
[
j
+
1
]
)
，
1
≤
i
<
n
t
[
i
]
[
j
]
,
i
=
n
t[i][j]=\left\{
对于1<=i<n，t[i][j]的每一个值仅依赖于t[i+1][j]和t[i+1][j+1]的值。通过以递减i的顺序来计算t[i][j]的值。
从上往下，如果每次选择的子结点对应的子塔数值最大，则父塔数值一定最大。
【法一】递归 将父结点对应的最优解转化为子结点对应的最优解。另设数组存储子塔最大值，减少重复计算。
【法二】递推 从下往上，算出各级子塔的最优解。
代码
【法一】递归
#include<iostream> #include<cstring> using namespace std; int max(int x,int y) {if(x>y) return x; return y;} int n,t[105][105],m[105][105];//m存储子塔最大值 int dfs(int i,int j){ if(m[i][j]>=0) return m[i][j]; if(i==n-1) return m[i][j]=t[i][j]; return m[i][j]=t[i][j]+max(dfs(i+1,j),dfs(i+1,j+1)); } int main(){ int c; cin>>c; while(c--){ int i,j; cin>>n; for(i=0;i<n;i++) for(j=0;j<=i;j++) cin>>t[i][j]; memset(m,-1,sizeof(m));//-1表示未扩展 cout<<dfs(0,0)<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
【法二】递推
#include<iostream> using namespace std; int max(int x,int y) {if(x>y) return x; return y;} int main(){ int c,t[105][105]={0}; cin>>c; while(c--){ int n,i,j; cin>>n; for(i=0;i<n;i++) for(j=0;j<=i;j++)//注意等号 cin>>t[i][j]; for(i=n-1;i>=0;i--) for(j=0;j<=i;j++) t[i][j]+=max(t[i+1][j],t[i+1][j+1]); cout<<t[0][0]<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
HDOJ-1087 Super Jumping! Jumping! Jumping!
题目
有一种跳棋游戏，棋子在棋盘上呈线性排列。除起点与终点外，每个棋子上都标着一个正整数。玩家必须从起点跳到终点，在途中可以访问棋子，但每次只能向前访问更大的棋子，也可以不访问棋子。玩家在途中访问的棋子的数值之和就是最终得分。求最大得分。
思路
描述最优子结构： 该问题（找出从1出发能得到的最大和）的最优解包含了子问题（找出从1右边的点出发能得到的最大和）的一个最优解。
利用子问题的最优解来构造原问题的一个最优解：
递归公式：设data[i]为第i个棋子的数值，则
dp[i]= data[i]+maxi<j≤ndp[j]
递归定义最优解的值： dp[i]的每一个值仅依赖于dp[j]（i<j≤n）的值。通过以递增i的顺序来计算。
程序
#include<iostream> using namespace std; int max(int a,int b) {if(a>b) return a; return b;} int main(){ int n,i,j,mdp; while(cin>>n&&n){ int data[1005]={0};//data存储各棋子数值，由于要用于判断，所以不能被和覆盖 int dp[1005]={0};//dp[i]表示从i出发能得到的最大和 for(i=1;i<=n;i++) cin>>data[i]; for(i=n;i>=0;i--){//最小从0出发 mdp=0; for(j=i+1;j<=n;j++)//查找从i出发能走到的格子 if(data[j]>data[i]) mdp=max(mdp,dp[j]); dp[i]=data[i]+mdp;//dp[i]=走到i得分+从下一步出发能得到的最大和 } cout<<dp[0]<<endl;//dp[0]为最终解 } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
【注】由于起点与终点具有对称性，从终点跳到起点得分是相同的，可以从前往后递推。
HDOJ-1176 免费馅饼
题目
有一天gameboy正走在回家的小径上，忽然天上掉下大把的馅饼。将小径视为数轴上一条线段，最小值为0，最大值为10，馅饼都掉在线段上的整数点，gameboy只能在线段上移动，0秒时他处于整数5的位置，每秒钟最多移动1米。求他最多可以接到的馅饼个数。
思路
本问题可画出与2084 数塔类似的塔状结构，表示玩家移动的路径。
易发现其与原始数塔的不同之处：多了辐射方向，第7层（第6秒）开始，层宽度不再增加。
描述最优子结构： 该问题（找出在第0秒从5出发的最大路线）的最优解包含了子问题（找出在第0秒从与5相邻的点出发的最大路线）的一个最优解。因此，在第0秒从顶点5出发的最大路线只能是三者之一：从顶点出发走到4，走在第1秒从4出发的最大路线；在5停留1秒，走在第1秒从5出发的最大路线；从顶点出发走到6，走在第1秒从6出发的最大路线。
利用子问题的最优解来构造原问题的一个最优解： 在求解状态（i,j）之前，dp[i][j] 存储第i秒在j位置落下的馅饼总数，求解之后表示第i秒从j出发得到的最大值。
递归公式：设tm为馅饼落下的最晚时刻，
i=tm时，dp[i][j]=dp[i][j]+0;
0<i<tm时，dp[i][j]=dp[i][j]+
{
m
a
x
(
d
p
[
i
+
1
]
[
0
]
,
d
p
[
i
+
1
]
[
1
]
)
，
j
=
0
m
a
x
(
d
p
[
i
+
1
]
[
j
−
1
]
,
d
p
[
i
+
1
]
[
j
]
,
d
p
[
i
+
1
]
[
j
+
1
]
)
，
1
≤
j
≤
9
m
a
x
2
(
d
p
[
i
+
1
]
[
9
]
,
d
p
[
i
+
1
]
[
10
]
)
,
j
=
10
\left\{
以资源换代码复杂度： 从数塔可以看出，在6层以上，某些状态是没有意义的，如（4 的顺序来计算。
代码
#include<cstdio> #include<cstring> int dp[100005][11];//输入时，dp[t][p]表示第t秒在p位置落下的馅饼总数 //处理时，dp[i][j]表示第i秒从第j个位置开始的最优解 int max2(int a,int b) {if(a>b) return a; return b;} int max3(int a,int b,int c) {if(a>=b&&a>=c) return a; if(b>=a&&b>=c) return b; return c;} int main(){ int n; while(scanf("%d",&n)&&n){ int i,j; memset(dp,0,sizeof(dp)); int t,p,tm=1;//tm代表最大时刻 for(i=0;i<n;i++) {scanf("%d%d",&p,&t);//题目坑点 if(t>tm) tm=t; dp[t][p]++;} for(i=tm-1;i>=0;i--){//各时刻 dp[i][0]+=max2(dp[i+1][0],dp[i+1][1]); for(j=1;j<=9;j++)//各位置 dp[i][j]+=max3(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]); //这一秒状态由下一秒状态而来，这一秒位置只能是上一秒位置或其左右 dp[i][10]+=max2(dp[i+1][9],dp[i+1][10]); } printf("%d\n",dp[0][5]); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
HDOJ-2602 Bone Collector
题目
有一个骨头收藏家带着一个容积为V的背包来到墓地收集骨头，每个骨头体积不同，价值也不同，求他能带走的骨头的价值总和的最大值。
思路
01背包原题
**最优子结构：**该问题（确定i个物品装到容积为j的背包产生的最大价值）的最优解包含了子问题（确定i-1个物品装到容积为j的背包产生的最大价值）的一个最优解。证明：令dp[i][j]表示i个物品装到容积为j的背包产生的最大价值。从i-1到i，多了一种骨头可供选择，可选择替换或不替换背包中原有的一个。若不替换，则dp[i][j]=dp[i-1][j]，dp[i-1][j]必须是最优的；若替换，须保证替换后取得更优解，则dp[i-1][j]必须是最优的。从j-1到j，背包容积增加1，可选择替换或不替换背包中原有的一个。若不替换，则dp[i][j]=dp[i-1][j]，dp[i-1][j]必须是最优的；若替换，须保证替换后取得更优解，则dp[i-1][j]必须是最优的。
利用子问题的最优解来构造原问题的一个最优解： 把问题转化为一个子问题和在子问题基础上做出的决策。在必须进行替换的情况下，最小代价是背包腾出新物品所需空间。至于为什么是dp[i-1][j-vo[i]]而不是dp[i][j-vo[i]]，是因为dp[i][j-vo[i]]考虑了物品i。
**递归定义最优解的值：**选择在状态（i,j）下的最优解的问题作为子问题，物品数量i=1,2,…,n。背包容积j=0,1,2,…,v。
我们的最终目标是确定在状态（n,v）下的最优解。当i=0时，dp[i][j]=0。递归公式：
{
0
，
i
=
0
m
a
x
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
j
−
v
o
[
i
]
]
+
v
a
[
i
]
)
,
i
≥
1
\left\{
对于i>=1，dp[i][j]的每一个值仅依赖于dp[i-1][j]和dp[i-1][j-vo[i]]的值。因此，先有dp[i-1][x]后有dp[i][x]，通过以递增i的顺序来计算dp[i][j]的值，j的值变化顺序任意。
空间复杂度优化：新计算出的dp[i][x]可以直接覆盖dp[i-1][x]，则dp[j]=
{
0
，
i
=
0
m
a
x
(
d
p
[
j
]
,
d
p
[
j
−
v
o
[
i
]
]
+
v
a
[
i
]
)
,
i
≥
1
\left\{
在计算dp[j]的时候需要引用dp[j-vo[i]]的值，因此以递减j的顺序来计算dp[j]的值，以避免dp[j-vo[i]]在被引用之前变化。
贪心解法错误的原因：对象量子性。由于对象不可分割，所以背包不一定装满。
代码
#include<iostream> using namespace std; int max(int a,int b) {if(a>b) return a; return b;} int main(){ int t; cin>>t; while(t--){ int n,v,i,j,va[1005]={0},vo[1005]={0},dp[1005]={0}; cin>>n>>v; for(i=1;i<=n;i++) cin>>va[i];//va存储物品价值 for(i=1;i<=n;i++) cin>>vo[i];//vo存储物品体积 for(i=1;i<=n;i++)//i代表物品数量（从1到n） for(j=v;j>=0;j--){//j代表背包容积（从0到v） if(j>=vo[i]&&dp[j-vo[i]]+va[i]>dp[j]) dp[j]=dp[j-vo[i]]+va[i]; //计算背包前一容积腾出第i个物品体积的情况下取得的最大价值与第i个物品价值之和 } cout<<dp[v]<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
HDOJ-1421 搬寝室
题目
从n件物品中选2*k件搬到另一个地方，每次搬一对。现定义一次搬运产生的疲劳度为这对物品的重量之差的平方。给定k及其他数据，求完成所有搬运任务后累计的疲劳度的最低值。
思路
可以证明，当每次提的物品重量相邻时，疲劳度最小。因此，首先对输入数据进行排序。
描述最优子结构： 该问题（在前i个物品中选择j对的最低疲劳度）的最优解包含了子问题（在前i-1个物品中选择j对的最低疲劳度 与 在前i-2个物品中选择j-1对的最低疲劳度）的一个最优解。证明：令dp[i][j]表示在前i个物品中选择j对的最低疲劳度。从i-1到i，多了一种物品可供选择，可选择替换或不替换原有的一对。若不替换，则dp[i][j]=dp[i-1][j]，dp[i-1][j]必须是最优的；若替换，须保证替换后取得更优解，则dp[i-2][j-1]必须是最优的。
利用子问题的最优解来构造原问题的一个最优解： 一般来说，i每增加2，j的最大取值便可增加1。由于j的最大取值会变化，将dp[i][j](j*2>i)记为无穷大，表示不可用。
递归公式：设m[i]为排序后第i个物品的重量，
d
p
[
i
]
[
j
]
=
{
0
，
i
=
0
或
j
=
0
m
i
n
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
2
]
[
j
−
1
]
+
(
m
[
i
−
1
]
−
m
[
i
]
)
2
)
,
i
≥
2
dp[i][j]=\left\{
递归定义最优解的值：dp[i][j]的每一个值仅依赖于dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]的值。通过以递增i的顺序来计算。
代码
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int dp[2005][1005];//dp[i][j]表示在前i个物品中选择j对的最低疲劳度 #define INF 32768000 bool cmp(int x,int y) {return x<y;} int min(int x,int y) {return x<y?x:y;} int main(){ int n,k,i,j; while(scanf("%d%d",&n,&k)!=EOF){ int m[2005]={0}; for(i=1;i<=n;i++) cin>>m[i]; sort(m+1,m+1+n,cmp); for(j=0;j<=k;j++) dp[0][j]=0;//第0行保留为0，使得第2行可以选择1对物品 for(i=1;i<=n;i++) for(j=1;j<=k;j++) dp[i][j]=INF;//dp[i][j]初始化为无穷大，使得以后可以新增 for(i=2;i<=n;i++) for(j=1;j*2<=i;j++) dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(m[i-1]-m[i])*(m[i-1]-m[i])); cout<<dp[n][k]<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
HDOJ-1069 Monkey and Banana
题目
给出一些砖块，堆叠砖块建塔。砖块有n种类型，每种类型数量不限，形状为长方体，且可以改变放置方向。如果上层砖块的长、宽必须小于下层砖块的长、宽，求塔的最大高度。
思路
而本问题则要求满足塔中面积相邻的两块砖之前满足一定关系，即上层砖比下层砖小。因此，最好先进行排序，按顺序进行建塔。然而，排序的操作对象只能是有限个数量。在这里要看出陷阱：同一类型、同一摆放位置的砖块只能使用一次。1种砖块有3个维度，对应6种摆放方式，等效看成6种砖。注意，本题中与问题有关的参数是子问题空间，与01背包中允许选择的物品数量类似。
最优子结构： 将1→6扩充后的各砖块先按长度，后按宽度进行排序。问题（前i个砖能构成的塔的最大高度）的最优解包含了子问题（前j（j<i）个砖能构成的塔的最大高度）的一个最优解。为什么是j而不是i-1：排序具有的两个标准是有优先级别区别的，并不能保证前一个的长、宽均比后一个大。证明：令dp[i]表示前i个砖能构成的塔的最大高度。对于任意前j（j<i）个砖能构成的塔，有且仅有两种情况：第i块砖可以放到顶层或不可以。如果可以，则对应的前j（j<i）个砖能构成的塔的高度必须是最大的。
利用子问题的最优解来构造原问题的一个最优解： 把问题涉及到一个子问题，该子问题需要在所有j<i的选择中选出最优。
递归定义最优解的值： 选择在状态（i）下的最优解的问题作为子问题，子问题空间i=1,2,…,len。（len为砖块总数）。注意dp[i]不一定是递增的，所以我们的最终目标是确定所有状态下的最优的解。
递归公式：
dp[i]=h[i]+max(0,dp[j]) (1<=j<i且a[i]<[j]且b[i]<b[j])
dp[i]的每一个值仅依赖于dp[j]的值。因此，通过以递增i的顺序来计算dp[i]的值。
代码
#include<iostream> #include<algorithm> using namespace std; int max(int a,int b) {if(a>b) return a; return b;} struct node {int x;int y;int z;}nd[185]; bool cmp(node a,node b) {if(a.x!=b.x) return a.x>b.x;//先比较a return a.y>b.y;}//后比较b int main(){ int n,i,j,t=0; while(cin>>n&&n){ int len=1;//len代表数组长度 for(i=0;i<n;i++){ int a,b,c; cin>>a>>b>>c;//3个数6种排列 nd[len].x=a;nd[len].y=b;nd[len].z=c; nd[len+1].x=a;nd[len+1].y=c;nd[len+1].z=b; nd[len+2].x=b;nd[len+2].y=a;nd[len+2].z=c; nd[len+3].x=b;nd[len+3].y=c;nd[len+3].z=a; nd[len+4].x=c;nd[len+4].y=a;nd[len+4].z=b; nd[len+5].x=c;nd[len+5].y=b;nd[len+5].z=a; len+=6; } sort(nd+1,1+nd+len,cmp); int dp[185]={0}; int imax=0,jmax;//imax存储最高塔的高度 for(i=1;i<len;i++){ jmax=0;//jmax存储在i之前最高塔的高度 for(j=1;j<i;j++){ if(nd[j].x>nd[i].x&&nd[j].y>nd[i].y) jmax=max(jmax,dp[j]); } dp[i]=nd[i].z+jmax; imax=max(imax,dp[i]); } cout<<"Case "<<++t<<": maximum height = "<<imax<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
USACO 2006 November Silver - Bad Hair Day
题目
n头奶牛站成一列(1≤n≤80000)，一只奶牛a可以看到前面比它矮的奶牛，但不能看到比它高或等的奶牛b及b之后的奶牛。输入奶牛的高度，输出每只奶牛可以看到的奶牛数量之和。
思路
奶牛的高度形成一个数列。
“俯视序列”：对于给定的i<j<=n+1，对于任意的i<k<j，有h[k]<h[i]，则称从i到j构成了一个“俯视序列”。
题目要求的就是i（1<=i<=n）的俯视序列的最大值之和。
i的俯视序列的最大值c[i]具有最优子结构：如果后面的牛i比前面j高，那么前面能看到的后面也能看到。最大俯视序列一直到比i高的牛为止。如果前面的牛能看到底，c[i]=c[j]+1；如果只能看到一部分，那么求出j的最大俯视序列，从该序列末尾后一个继续判断，c[i]为所有最大俯视序列之和。
代码
#include<iostream> using namespace std; const int N = 8e4 + 5; int main(){ int n,h[N],c[N]; int hm[N];//hm[i]看到的第一只比i高的牛的编号 cin >> n; for(int i = 1; i <= n; i++) cin >> h[i]; c[n]= 0; hm[n]= -1;//h[m]为-1代表没有牛比i高 long long sum=0; for(int i = n-1; i >= 1; i--){ //从前往后遍历每只奶牛 bool can = true;//can不仅仅代表是否能看到，而是结果是否产生 c[i] = 0; for(int j = i+1; can;){ //对于每只奶牛，从后往前逐只看 if(h[i] <= h[j]){ //比我高，看不见 can = false; hm[i] = j; sum += c[i]; } else{ if(hm[j] == -1){ //j是j~n中最高的 hm[i] = -1; c[i] += c[j] + 1; sum += c[i]; can = false; } else{ c[i] += c[j] + 1; j = hm[j]; } } } } cout<<sum<<endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
HDOJ-1160 FatMouse’s Speed
题目
输入包含多组数据，每组为一个老鼠序列，包含每只老鼠的体重与速度信息，输出长度最大的序列的长度及老鼠编号（其在原序列中出现的顺序），满足体重递增、速度递减。
思路
将输入数据首先按体重递增排序，其次按速度递减排序，这样，按顺序遍历各老鼠时，体重递增的要求自动满足。题目可抽象为寻找一个最长递减子序列。
考虑到子序列中的元素是离散分布在原系列当中的，题目又要求输出序列元素，可采取链表式的结构存储信息。一个结点中有2个成员，len表示子串最大长度，next表示下一项编号，将一项添加到链表末尾称为“连接”，其操作为：记该项的len为末项len+1，该项的next为末项编号。
dp[i].len=1+0,m[i].s>m[i+1].s1+maxi+1<j≤ndpj.len,mi.s≤m[i+1].s
代码
#include<cstdio> #include<algorithm> using namespace std; struct mice {int w;int s;int num;}m[1005]; bool cmp(mice x,mice y) {if(x.w!=y.w) return x.w<y.w;//体重递增排序 return x.s>y.s;}//速度递减排序 int main(){ int n=1; while(scanf("%d%d",&m[n].w,&m[n].s)!=EOF) {m[n].num=n;n++;} n-=1; sort(m+1,m+1+n,cmp); int i,j,sm=1,len=1,lenm=1; struct dongp{int len,next;}dp[1005]={0};//dp[i]存储从m[i]开始的子串的有关信息 for(i=1;i<=n;i++) {dp[i].len=1;dp[i].next=9999;} for(i=n-1;i>=0;i--){//从后往前遍历 if(m[i].s>m[i+1].s){//当前项比后一项大 if(dp[i+1].len==1){//序列刚开始 //将dp[i+1]与max(dp[j])(i+1<j<=n)连接 int lenm2=0; for(j=i+2;j<=n;j++){ if(m[j].s<m[i+1].s&&dp[j].len>lenm2) {lenm2=dp[j].len;dp[i+1].next=j;} } dp[i+1].len+=lenm2; } //将dp[i]与dp[i+1]连接，用到更新后的dp[i+1] dp[i].next=i+1; dp[i].len=dp[i+1].len+1; } //序列结束，更新最长子序列 else if(dp[i+1].len>lenm) {lenm=dp[i+1].len;sm=i+1;} } printf("%d\n",lenm); int ele=sm; do{printf("%d\n",m[ele].num); ele=dp[ele].next;} while(ele!=9999); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
HDOJ-1159 Common Subsequence
题目
给定一个序列X=<x1，x2，…，xm>，定义其子序列为原序列中去掉一个或多个元素，剩余元素保持先后顺序形成的序列。给定两个序列X和Y，求X和Y的最长公共子序列的长度。
思路
LCS的最优子结构
设X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>为两个序列，并设Z=<z1,z2,…,zk>为X和Y的任意一个LCS。
1）如果x[m]=y[n]，那么z[k]=x[m]=y[n]而且Z(k-1)是X(m-1)和Y(n-1)的一个LCS。
2）如果x[m]≠y[n]且z[k]≠x[m]，那么Z是X(m-1)和Y的一个LCS。
3）如果x[m]≠y[n]且z[k]≠y[n]，那么Z是X和Y(n-1)的一个LCS。
两个维度：序列X的长度和序列Y的长度。
一个递归解
在找X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的一个LCS时，可能要涉及一个或两个子问题。如果x[m]=y[n]，那么必须找出X(m-1)和Y(n-1)的一个LCS。如果x[m]≠y[n]，就必须解决两个子问题：找出X(m-1)和Y的一个LCS，以及找出X和Y(n-1)的一个LCS。这两个LCS中，较长的就是X和Y的一个LCS。问题具有重叠子问题性质：为找出X和Y的一个LCS，可能需要找出X(m-1)和Y的一个LCS以及X和Y(n-1)的一个LCS，而这两个问题都包含着找X(m-1)和Y(n-1)的一个LCS的子子问题。
定义c[i,j]为序列X(i)和Y(j)的一个LCS的长度。
c[i][j]=0,i=0或j=0ci-1,j-1+1,i>0且j>0且xi=y[j]max(ci,j-1,ci-1,j),i>0且j>0且xi≠y[j]
参考代码
#include <stdio.h> #include <string.h> #define SIZE 1001 #define max(a,b) ((a)>(b)?(a):(b)) int dp[SIZE][SIZE]; char a[SIZE],b[SIZE]; int main(){ while(scanf("%s%s",&a,&b)!=EOF){ memset(dp,0,sizeof(dp)); int lena=strlen(a); int lenb=strlen(b); for(int i=0;i<lena;i++) for(int j=0;j<lenb;j++) if(a[i]==b[j]) dp[i+1][j+1]=dp[i][j]+1; else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]); } printf("%d\n",dp[lena][lenb]); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
总结
不要妄想一步登天。“子序列”本身也是一种数据集合，因此其可能存在最优子结构。不要一开始就想着解的最优子结构。
善用代数工具，学会抽象定义：两个序列的最长子序列也是序列
HDOJ-1058 Humble Numbers
题目
如果一个数的因数只有2，3，5，7（含它们的倍数），则称这个数为丑数。输入正整数n（1 <= n <= 5842），输出第n个丑数的值。
思路
第一个丑数为“1”，后面的每一个丑数都是由已经生成的丑数乘2、3、5或7而来，那么后一个丑数就是已经生成的丑数乘2、3、5或7得到的最小值
第一个：1
第二个：1*2,1*3,1*5或1*7中最小为2，2已乘过第1个丑数，更新为2与第2个丑数相乘
第三个：2*2,1*3,1*5或1*7中最小为3，3已乘过第1个丑数，更新为3与第2个丑数相乘
第四个：2*2,2*3,1*5或1*7中最小为4，2已乘过第2个丑数，更新为2与第3个丑数相乘
……
参考代码
# include<stdio.h> # define MAX 5842 __int64 num[MAX+1]; __int64 min(__int64 a,__int64 b,__int64 c,__int64 d){ __int64 min1,min2; min1=a<b?a:b; min2=c<d?c:d; if(min1<=min2) return min1; else return min2; } int main(){ int i=1,n; num[1]=1; int p2,p3,p5,p7; p2=p3=p5=p7=1;//p2,p3,p5,p7分别代表2，3，5，7乘的丑数序号 while(i<MAX){ num[++i]=min(num[p2]*2,num[p3]*3,num[p5]*5,num[p7]*7); if(num[i]==num[p2]*2) p2++; if(num[i]==num[p3]*3) p3++; if(num[i]==num[p5]*5) p5++; if(num[i]==num[p7]*7) p7++; } while(scanf("%d",&n)!=EOF){ if(n==0) break; else{ if(n%10==1&&n%100!=11)//eleventh printf("The %dst humble number is %lld.\n",n,num[n]); else if(n%10==2&&n%100!=12)//twelfth printf("The %dnd humble number is %lld.\n",n,num[n]); else if(n%10==3&&n%100!=13)//thirteenth printf("The %drd humble number is %lld.\n",n,num[n]); else printf("The %dth humble number is %lld.\n",n,num[n]); } } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
