下载

0下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 高二下期4月17日下午动态规划专项练习(1)

高二下期4月17日下午动态规划专项练习(1).doc

高二下期4月17日下午动态规划专项练习(1)

faint
2018-09-07 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《高二下期4月17日下午动态规划专项练习(1)doc》,可适用于工程科技领域

安阳一中信息学奥赛辅导资料动态规划专项练习()题目名称警卫安排最长上升子序列最短回文串青蛙的烦恼提交程序securitypasccpplispaspalindromepasfrogpas输入文件securityinlisinpalindromeinfrogin输出文件Securityoutlisoutpalindromeoutfrogout时间限制ssss内存限制MBMBMBMB、警卫安排(securitypasccpp)一个重要的基地被分为n个连通的区域。出于某种神秘的原因这些区域以一个区域为核心呈一颗树形分布。在每个区域安排警卫所需要的费用是不同的而每个区域的警卫都可以望见其相邻的区域只要一个区域被一个警卫望见或者是安排有警卫这个区域就是安全的。你的任务是:在确保所有区域都是安全的情况下找到安排警卫的最小费用。输入数据第一行n表示树中结点的数目。接下来的n行描述了n个区域的信息每一行包含的整数依次为:区域的标号i(<i<=n)在区域i安排警卫的费用k区域i的子结点数目m接下来m个数为区域i的子结点编号。输出数据一行一个整数为最小的安排费用。样例输入:securityin输出securityout数据范围对于所有的数据<n<=。、最长上升子序列(LISpasccpp)LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列你还能解决吗?给出一个长度为N整数序列请求出它的包含第K个元素的最长上升子序列。例如:对于长度为的序列<,,,,,>它的最长上升子序列为<,,,>但如果限制一定要包含第个元素那么满足此要求的最长上升子序列就只能是<,,>了。输入数据第一行为两个整数N,K如上所述。接下来是N个整数描述一个序列。输出数据请输出一个整数即包含第K个元素的最长上升子序列长度。样例输入输出数据范围对于所有的数据满足<n<=<k<=n、最短回文串(palindromepasccpp)如果一个字符串正过来读和倒过来读是一样的那么这个字符串就被称作回文串。例如abcdcbaabcddbca就是回文串而abcdabcd不是。你要解决的问题是:对于任意一个字符串输出将这个字符串变为回文串需要插入的最少字符个数比如abbd只需要插入个字符就可以变为一个回文串。输入数据第一行是一个整数N第二行是一个长度为N字符串S输出数据一行一个整数表示将S变为回文串需要插入的最小字符个数样例输入abbd输出数据范围对于所有数据<n<=、青蛙的烦恼(frogpasccpp)池塘中有n片荷叶恰好围成了一个凸多边形有一只小青蛙恰好站在号荷叶上小青蛙想通过最短的路程遍历所有的荷叶(经过一个荷叶一次且仅一次)小青蛙可以从一片荷叶上跳到另外任意一片荷叶上。输入数据(frogin)第一行为整数n荷叶的数量。接下来n行每行两个实数为n个多边形的顶点坐标按照顺时针方向给出。保证不会爆double。输出数据(frogout):遍历所有荷叶最短路程请保留位小数。样例输入:frogin输出:frogout数据范围:对于所有数据,<n<=第页共页

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/3

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利