博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
解题报告 Valentine‘s seat
阅读量:4839 次
发布时间:2019-06-11

本文共 1388 字,大约阅读时间需要 4 分钟。

 

1.        题目

1Valentine’s Seat(seat)

描述

今天是情人节的前一天,小杉还在电影院打工(惨啊)。

老板很懂得情人节的情调,要小杉提前做好准备,那么现在给小杉的任务是对电影院的座椅上色。

电影院总共n+1m+1列的椅子排成一个矩阵。第一行的椅子已经全部上了粉红色,第一列从第二个开始的椅子已经全部上了天蓝色。

一个可爱的上色方案应该满足除了第一行第一列以外,对任意的一个椅子,它的颜色应当和它左边的一把椅子(同行)或上面的一把椅子(同列)颜色相同。

小杉现在想知道总共有多少种可爱的上色方案。

输入格式

一行两个整数n,m(1<=n,m<=3000)

输出格式

仅有一行,一个整数,为上色方案数对19900801取模的结果

样例输入

1 1

样例输出

2

样例解释

唯一可上色的一把椅子,不是粉红就是天蓝,怎样都是可爱的

 

2.        题目实质

求一种特殊的 01 矩阵。

3.        算法

递推,其实这也是一个数学题。

抽象出模型,就是01矩阵的问题,问题即为求最上一行全是1,最左一列全是001矩阵,任意一个元素与其前趋或上继相同的情况数。而这种情况等价于任意一行的0的个数大于等于上一行的0的个数(假如比上一行少的话,上一行多出的0的下继为1,这个1不满足题意)。

接下来就很简单了,我们令f[n,k]为第n+1行有k+10的情况,则

f[n,k]=sum{f[n-1,j]}(j=1..k)

简单变换得

f[n,k]=f[n-1,k]+f[n,k-1]

初始状态为f[0,0]=1,结果为f[n,m] (f[n,m]=sum{f[n-1,j]}(j=1..m))

空间限制的问题,使用滚动数组可以解决。

其实仔细观察的话,会发现结果就是C(n+m,n)

注意 n=0 ( 0 ) ,或是 k=0 (这一行这有最边上那一个零) f=1

 

4.        注意事项

话说这个题我的式子推对了,初始化打错了 XD

所以,注意初始化啊啊。

5.        时空复杂度

O(n,m)

6.        程序代码

LZYstd  pascal

const

 k=19900801;

var

 a:array[0..3000,0..3000]of longint;

 n,m:longint;

 i,j:longint;

 

begin

assign(input,'seat.in');reset(input);

assign(output,'seat.out');rewrite(output);

readln(n,m);

for i:=1 to n do a[i,0]:=1;

for i:=1 to m do a[0,i]:=1;   //此处第一行为第 0

 

for i:=1 to n do begin

 for j:=1 to m do begin

  a[i,j]:=(a[i-1,j]+a[i,j-1])mod k;

 end;

end;

 

if(a[n,m]<0)then writeln(a[n,m]+k) else writeln(a[n,m]);  //防止 mod 过头

close(input);

close(output);

end.

转载于:https://www.cnblogs.com/SueMiller/archive/2011/08/09/2132317.html

你可能感兴趣的文章
计算机组成原理复习
查看>>
BUPT复试专题—中序遍历序列(2013)
查看>>
【常见Web应用安全问题】---7、CRLF injection
查看>>
php7.2.1 安装
查看>>
用winrar解压时提示无法设置安全数据 拒绝访问的解决方法
查看>>
诡异的数学,数字问题 - leetcode
查看>>
交换输出
查看>>
设计模式-策略模式&状态模式&访问者模式
查看>>
python学习第三十三节(IO模型)
查看>>
linux pci 驱动小结
查看>>
BZOJ2744: [HEOI2012]朋友圈
查看>>
设计模式之抽象工厂模式
查看>>
大整数相关的几道题
查看>>
利用表格实现大图轮播
查看>>
SpringBoot集成jsp
查看>>
HTML+CSS 内容居中效果
查看>>
关于对话框
查看>>
Jmeter-元件的作用域和执行顺序
查看>>
ArrayList集合
查看>>
Redis集群搭建与简单使用
查看>>