动态规划例题-刘汝佳_第1页
动态规划例题-刘汝佳_第2页
动态规划例题-刘汝佳_第3页
动态规划例题-刘汝佳_第4页
动态规划例题-刘汝佳_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、动态规划例题版本20071002清华大学 刘汝佳HandsShakingn=50个人坐在圆桌上握手，要求每个人恰好和一个人握手，但是手不许交叉。例如四个人有两种握法。统计握法总数。RGBStreets你需要给一些房子着R，G，B三色之一， 相邻的房子必须着不同的颜色。已知每个房子着每种颜色的花费，用尽量少的花费给每个房子着上色。UnsealTheSafe在键盘上可以随便按一个键开始，然后每次按与上次相邻的数字。一共按n次键，一共可以组成多少个数字串？FenceRepairing你有一些Fence，但是其中一些破了。你希望修复它们。每次可以修复一个区间i,i+1, ., j，代价是sqrt(j-

2、i+1)。用最小的代价修复所有的破Fence。注意： 你可以修复一个本来就没破的Fence。TableSeating你的餐厅有n=12个座位排成一排。每次会进来一组人，恰好有i个人的概率为pi%。这i个人将等概率的随机选择连续的i个座位坐下来。如果找不到就离开（每个人一旦坐下来就不会离开）。求第一次有人离开时，有人的座位数目的数学期望。LastStoneBob和Sally玩取石子游戏，每次都是Bob先走，然后Sally走.这样一直轮流走，直到所有石子都被取走。取走最后一个石头者获胜。每次双方可以拿走的石子个数在数组turns中，保证1一定包含在turns中。石子数为m, m+1, ., n的游

3、戏中有多少个是Bob必胜？（假设双方均采取最优策略）ZigZag给一个长度为n=50的整数序列，求它的最长ZigZag子序列（删除0个或多个数，其他数顺序不变）的长度。ZigZag序列的定义是相邻两数的差正负交替（相邻元素不能相等）BadNeighbors给一个长度为n=40的环型正整数序列，选择不相邻的若干个数，使它们的和尽量大。AvoidRoads一个w*h(1=w,h=100)网格，有一些边不能行走。求左下的到右上的路径数目（每次只能往右、上走）。ChessMetric在n*n(3=n=50)棋盘上有一个超级马（马+国王）。走恰好k(1=k=50)步，且中间不能离开棋盘，求方案数。QuickSums给一个数字串，插入尽量少的加号，使得运算结果为给定数K。例如从382834得到100可以38+28+34，或者3+8+2+83+4，或者3+82+8+3+4，至少需要2个加号。数字串不超过10个字符，0=K=100BlockCounter压缩词 单个字符：A, B 连接：ST 压缩：(X,S)，其中X是19的整数例如(2,A(3,AB)为AABABABAABABAB给长度不超过50的压缩串S，统计它有多少个连续相同串ChangingSounds给一个整数数列，第一个数为B。给出长度为n的修改序列Ci（均为正整数），从第一个数开始每次可以加Ci或减Ci，要求

人人文库> 全部分类> 应用文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论