集训队作业画家工作室_第1页
集训队作业画家工作室_第2页
免费预览已结束，剩余1页可下载查看

下载本文档

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

文档简介

的方格矩形。尺寸为i的矩形包含2i行、2i列，并且在某些行与列的交点处有洞。定义尺寸为0的矩形是一个洞。对于i>0，尺寸为i的矩形可以划分为四个尺寸为i-1的矩形，见下图：没有尺寸为i-的矩尺寸为i-的矩尺寸为i-的矩图中位于右边以及左下位置的都是尺寸为i-1的矩形。而左上位置一个2i1*

的完整正方形（无洞。完整的油画就是这样构造的首先，给出三个非负整数n，a，b。然后，拿出两个尺的一张向右移动a列，向上移动b行。最后，这个样本移到一比如，考虑下面这两个尺寸为2的矩形[输入输入文件“MAL.IN”的首行包含了一个数n，0<=n<=100，表示用来做油画的矩形的尺寸。接下来的两行分别给出了ab，0<=a,b2n。a表示向右移动的列数，b表示向上移动的行数。[输出[输入示例222[输出示例3MAL解题报[题意分析POI9801x

ab个单位。在第二个正方形中对应的坐标为(x+b,y-a)。的(x,y)[约定ssSk1Sk (sk位二进制数，0<=Si<=1，0<=i<k)[算法分析一个应该符合的条件是什么。n 洞：(0,1)(1,0) 洞：(0,3)(1,2)(1,3)(2,1)(2,3)(3,0)(3,1)(3,2)观察后，可以得出有关洞的几个结论在边长为2n的正方形中，设(x,y)为一个洞的坐标，那么在2n+1的正方形中(x+2n,y)是一个洞(x,y+2n)是一个洞(x+2n,y+2n)是一个洞不（x，y<2n不(0Xn

X Yn

Y12100 。

1X0

1X0

是根据这四条结论，可以得出如下定理是定理*在边长为2n的正方形中，如果坐标(x,y)满足：对于任一个满足0<=I<nI，XiYi中至少有一个不为0，那么(x,y)对应的格子为一个 把x+b、y-a这两种十进制的运算都变为二进制来考虑。下面 用动态规划求解坐标的个数xy0~I-1位已经确定且满足定理*x+b、y-a0~I-1也可以计算出来，并且，x+bIp，y-aI位上产XI-1XI-2……X1 pBI-1BI-2B1B0RI-1RI-2R1

YI-1YI-2……Y1 qAI-1AI-2A1A0TI-1TI-2……T1T0F(I,p,q)表示(I,p,q)对应的状态总数，亦即有多少个(x,y)I位满足pq。很自然的，想到用I来划分阶段，共有n个阶段。下面，设法I-1I个阶段之间架起桥梁。RI≡XI+BI+p(mod TI≡YI-AI-q(mod p’=q’=-[(YI-AI- （XiYi0，满足定理* （RiTi0，满足定理*（表示取下整，[-0.5]=-满足上面五个式子的两个状态(I+1,p’,q’)与(I,p,q)可以实现转化——即F(i1,p',q')

F(i,p,0XI,YI,XI,YIp,qp',q'/r

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论