DMKaplony's OI Blog

Fly my OI Dreams with CC...

公告

OI...
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

统计

  • 随笔 - 6
  • 文章 - 0
  • 评论 - 0
  • 引用 - 0

常用链接

留言簿(2)

随笔分类(7)

随笔档案(6)

文章分类

搜索

  •  

最新评论

阅读排行榜

评论排行榜

PKU2663 Tri Tiling
简单的DP,好像NOIP之前就做过这样的题。
这次仍然是很暴力的转移。。(好像我比较喜欢这个,省脑子。)

PKU2663



我认为我这个是纯粹的省时省心省脑的方法(话说last7还是后来加上去的)。
其实有更为精妙的数学方法:
【引用PKUDiscuss:
Posted by denghongchao at 2009-08-14 18:43:58 on Problem 2663
先假设没2竖为1 单位。
对当前解a[i] ,有
1.在此处放一单位的积木。等于a[i-1]*3;
2.与前面相连接。连接的方案有 2 * (a[i-2] + a[i-3] +......+a[0]);
a[i] = 3*a[i-1] + 2*(a[i-2] + a[i-3] +......+a[0]);
a[i-1] = 3*a[i-2] + 2*(a[i-3] + a[i-3] +......+a[0]);
a[i-1] - a[i-2] = 2*(a[i-2] + a[i-3] +......+a[0]);

解得a[i] = a[i-1] * 4 - a[i-2];
至于为何要a[0] = 1,从公式中就可看到因为要一直取到最前面一个单位。这时也有2种情况。故a[0] = 1 能从理论上运算。。。。这是我的理解,见笑了。

话说我还没怎么懂这个公式。。。

posted on 2010-03-03 15:00 DMKaplony 阅读(286) 评论(0)  编辑 收藏 引用 所属分类: PKU/POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理