‍某中学有一个开水房，只有一个供热水龙头，课间时，会有很多同学去排队打开水，同学们的水瓶大小不一，每个同学打水时都会将自己的水瓶装满。管理开水房的师傅是个聪明人，他想到了一个排队方案，也就是同学们按照他给出的排队方法，可以使同学们的平均等待时间最短。你分析一下，给出这个排队的方法，假定有n个人，第i个同学打水所需要的时间为ti，并给出平均等待时间的计算公式（）。（注意：第i个同学的等待时间包含前i-1个的打水时间和+自己打水的时间ti）‌

多项选择题可用动态规划算法解决的问题需要满足几个基本要素，从下面选项中找出这些基本要素（）。

A.重复子问题
B.阶段性
C.无后向性
D.最优子结构性质

单项选择题0-1背包问题：现有一背包容量c=5，n=4。4个物品分别为：（Wi，Vi）∣（1，3），（3，6），（4，9），（2，7）。如下m表中m[i][j]是前i个物品装背包容量为j时的最优值。其中第四行的数据没有填写，分析问题，将第四行的数据从如下选项中找出（）。

A.0，3，3，6，8，15
B.0，3，7，7，10，13
C.0，3，7，10，10，13
D.0，3，7，10，13，15

单项选择题‎凸多边形的三角剖分问题。用动态规划算法求解最优三角剖分，首先要分析最优解的结构，也就是将问题分解为子问题，并具有最优子结构性质。下图是一凸6边形（ABCDEF）的二种不同划分为子问题的方法，哪种是正确的将问题划分为子问题的方案？正确的划分方案共有几种不同方式？（）

A.右图正确，4种
B.右图正确，9种
C.左图正确，4种
D.左图正确，9种

单项选择题矩阵连乘问题：下图是动态规划算法计算6个矩阵A1A2A3A4A5A6连乘所生成的信息表（a）表描述了计算顺序（b）表是m[i][j]的最优值表（c）表是辅助信息表（断开位置）分析表格，给出A2A3A4A5A6五个矩阵连乘所需要的最少数乘次数，并用加括号的方法表示出其乘法顺序（）。

A.15125，（A2A3）（（A4A5）A6）
B.10500，（A2（A3A4））（A5A6）
C.15125，（A2（A3A4））（A5A6）
D.10500，（A2A3）（（A4A5）A6）

单项选择题动态规划解题的步骤分为四步：（1）分析最优解的结构（2）建立递归关系（3）计算最优值（4）构造最优解关于这四个步骤的内容描述不正确的是哪个？（）

A.计算最优值：以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值
B.构造最优解：根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造
C.建立递归关系：建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到
D.分析最优解的结构：一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质