文档章节

动态规划之合唱队形问题

一贱书生
 一贱书生
发布于 2016/11/22 10:21
字数 1126
阅读 43
收藏 0
点赞 0
评论 0

问题描述:

  N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,而不改变其他同学的位置,使得剩下的K位同学排成合唱队形。合唱队形要求:设K位同学从左到右 依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,则他们的身高满足 T1<T2...<Ti>Ti+1>…>TK(1<=i<=K)。已知所有N位同学的身高,计算最少需要几位 同学出列,可以使得剩下的同学排成最长的合唱队形。 

问题分析:

  假设第i位同学为个子最高的同学,我们先对其左边的同学求最大上升子序列,再对其右边的同学求最大下降子序列,然后两者相加再减1(第i位同学被重复计算 了一次),便得到第i位同学为最高个时所能排成的最长合唱队形。如果我们对这N位同学都执行此操作,便可得到每位同学为最高个时所能排成的最长合唱队形, 选取其中最长的合唱队形作为最终的结果。  

 从 上述的分析可以看出,我们可以将问题分成互相不独立的子问题,只要得到子问题的最优解,便可得到整个问题的最优解。我们可以用一张表来记录所有已解决问题 的答案,从而避免了重复计算。这里的一个关键问题便是:如何得到第i位同学的最大上升子序列和最大下降子序列。假如这N位同学的身高分别 为:176,163,150,180,170,130,167,160,我们用up[i]来记录第i位同学的最大上升子序列。如果要得到180同学为最高 个时的最大上升子序列即up[4],我们只需求出前3位同学所能形成的最大上升子序列,将其加1即可;要得到前3位同学所形成的最大上升子序列,便要求得 前2位同学的最大上升子序列,再加上1即可;同样要得到前2位同学的最大上升子序列,便要求得第1位同学的最大上升子序列。因此这是一个递推关系,只要我 们将前i个同学为最高个时做形成的最大上升子序列的值记录下来,取其中最大值加1便可得到第i位同学的最大上升子序列即up[i]。同理我们用 down[i]来记录第i位同学的最大下降子序列,只要我们将后(N-i)位同学每位同学为最高个时的最大下降子序列记录下来,取其中最大者再加1便可得 到第i位同学为最高个时的最大下降子序列即down[i]。那么,第i位同学为最高个时做能形成的最长合唱队形的长度为up[i]+down[i]-1。 求得所有同学为最高个时所能形成的最长合唱队形的长度,取其中最大值为最终的结果。

[java] view plain copy

 

  1. public class Main {  
  2.     public static void main(String[] args) {  
  3.         int []high={176,163,150,180,170,130,167,160};  
  4.         int []up=new int[8];   //记录每位同学的最大上升子序列  
  5.         int []down=new int[8]; //记录每位同学的最大下降子序列  
  6.         for(int i=0;i<high.length;i++){  
  7.             up[i]=1; //每位同学的最大上升子序列初始值为1  
  8.             for(int j=0;j<i;j++){  
  9.                 if((high[j]<high[i])&&(up[i]<up[j]+1)) up[i]=up[j]+1; //前i位同学的最大上升子序列的最大值再加1  
  10.             }  
  11.         }  
  12.         for(int i=high.length-1;i>=0;i--){  
  13.             down[i]=1;  
  14.             for(int j=high.length-1;j>i;j--){  
  15.                 if((high[j]<high[i])&&(down[i]<down[j]+1)) down[i]=down[j]+1; //后N-i位同学的最大下降子序列的最大值再加1  
  16.             }  
  17.         }  
  18.         int max=0; //设每位同学所形成的最长合唱队形的最大值初值为0  
  19.         int index=0; //设最大值对应的索引为0  
  20.         for(int i=0;i<high.length;i++){  
  21.             if(up[i]+down[i]-1>max) {  
  22.                 max=up[i]+down[i]-1; //求得每位同学所形成的最长合唱队形的最大值  
  23.                 index=i;  //求得对应的索引  
  24.             }  
  25.         }  
  26.         System.out.println("最长合唱队形的长度为:"+max);  
  27.         System.out.println("对应的是第"+(index+1)+"位同学,需要"+(high.length-max)+"位同学出列");  
  28.   
  29.     }  
  30. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 723
码字总数 600072
作品 0
算法:Dynamic Programing

一、动态规划干嘛的 二、可以解决哪些问题 动态规划一般可分为:线性动规,区域动规,树形动规,背包动规四类。 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等; 区域动规:石子...

猫咪要感冒
2016/10/09
1
0
技术解析:如何实现K歌App中的实时合唱

之前我们解析过很多社交直播App中不同场景的开发,比如在线K歌、小程序直播、多人视频聊天、AR等。 我们最近在知乎看到了一个问题「为什么k歌软件始终没有开发出实时合唱功能?」,我们只在知...

Agora
05/31
0
0
信息学奥赛一本通(C++版) 第二部分 基础算法 第九章 动态规划

信息学奥赛一本通(C++版) 第二部分 基础算法 第九章 动态规划 第一节 动态规划的基本模型 //1258 【例9.2】数字金字塔 //动态规划,自底向上计算,找出当前节点的最大值,一步一步推到顶点...

mrcrack
2017/11/03
0
0
白话版 动态规划法

关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷leetcode的时候,发现了一个很不错的关于动态规划算法的例题,特来分享一下! 这是...

木子昭
01/31
0
0
算法设计与分析(二)之动态规划

第一篇: 算法设计与分析之分治思想 动态规划(Dynamic Programming) 求解过程是多阶段决策过程,每步处理一个字问题,可用于求解组合优化问题 适用条件:问题要满足优化原则或最优子结构性质...

wenhui12345
2017/11/12
0
0
分治法,动态规划及贪心算法感悟

分治法,动态规划法,贪心算法这三者之间有类似之处,比如都需要将问题划分为一个个子问题,然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。 1.分治法 分治法(d...

努力的C
2017/10/16
0
0
动态规划算法秘籍

本文来自通俗易懂算法入门书《趣学算法》。 动态规划是1957年理查德·贝尔曼在《Dynamic Programming》一书中提出来的,八卦一下,这个人可能有同学不知道,但他的一个算法你可能听说过,他和...

rainchxy
2017/12/26
0
0
算法设计策略----动态规划法

动态规划法:与贪心法类似,动态规划法也是一种求解最优化问题的算法设计策略。它也采取分布决策的方法。但与贪心法不同的是,动态规划法每一步决策依赖子问题的解。直观上,为了在某一步做出...

Superheros
03/10
4
0
动态规划算法思想解决找零钱问题

动态规划算法思想解决找零钱问题 前言 关于找零钱问题,网上已经有很多相关的资料以及优秀的文章博客等。这里写这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受...

niaonao
2017/10/16
0
0
递归和动态规划

递归算法就是通过解决同一问题的一个或多个更小的实例来最终解决一个大问题的算法。为了在C语言中实现递归算法,常常使用递归函数,也就是说能调用自身的函数。递归程序的基本特征:它调用自...

LoSingSang
03/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Xamarin Essentials教程地理定位Geolocation

Xamarin Essentials教程地理定位Geolocation 通过地理定位功能,应用程序可以获取用户的当前地理位置,如经纬度值。利用地理位置,可以在地图上定位,也可以转化物理位置,划分用户的归属地。...

大学霸
15分钟前
0
0
vue 编译警告 Compiled with 4 warnings

There are multiple modules with names that only differ in casing. This can lead to unexpected behavior when compiling on a filesystem with other case-semantic. Use equal casing.......

落雪飞声
19分钟前
0
0
开篇文章,长期记录安全情形

密码位置 密码位于注释中 密码位于服务器端文件中 通过访问根目录下.htaccess、robots.txt查看禁查路径 密码文件可能存在的路径:/、/extra/、/extras/ 密码加密 binary to base16 sha256 彩虹...

hirainn
32分钟前
0
0
mysql数据库设置root可以远程登录的方法

mysql数据库设置root可以远程登录的方法 Posted on 2018-02-21 21:08 sishuisufeng 阅读(161) 评论(0) 编辑 收藏 允许root用户在任何地方进行远程登录,并具有所有库任何操作权限,具体操作如...

rootliu
37分钟前
1
0
TensorFlow 图的基本操作

图的创建,一般只需要使用默认图就能满足大部分的需求了 # 1 创建图的方法# 在默认图中创建常量c = tf.constant(0.0)# 新建一个图g = tf.Graph()# 设置上下文管理器,标明操作...

阿豪boy
今天
0
0
git 忽略文件失效

git update-index --assume-unchanged */.project

林子大鸟
今天
1
0
实现验证码功能

1、实现验证码,并存储 import com.dtb.pc_enterprise.entity.EnterUserEntity;import com.dtb.pc_enterprise.service.AdminService;import com.dtb.pc_enterprise.util.RedisService;......

木九天
今天
0
0
iptables 实例

以下部分内容为网络查询并整理结果 filter表小案例 iptables规则五条链:PREROUTING,INPUT,FORWARD,OUTPUT,POSTROUTING 四个表:filter nat mangle raw ###netfilter和iptables说明: 1、 ne...

李超小牛子
今天
0
0
Java面试基础篇——第六篇:常见Map类的区别

常见的map类有: HashMap, ConcurrentHashMap (Jdk1.8) , LinkedHashMap, TreeMap, Hashtable。 其中我们最常用的莫过于HashMap, 和并发情况下使用的ConcurrentHashMap了,它们的主要区别就在...

developlee的潇洒人生
今天
2
0
spring-boot:run启动时,指定spring.profiles.active

Maven启动指定Profile通过-P,如mvn spring-boot:run -Ptest,但这是Maven的Profile。 如果要指定spring-boot的spring.profiles.active,则必须使用mvn spring-boot:run -Drun.profiles=test......

夜黑人模糊灬
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部