ACM PKU 2663 Tri Tiling 简单的动态规划有趣

http://acm.pku.edu.cn/JudgeOnline/problem?id=2663
开始想复杂了,其实是个递推,或者说是个简单的动态规划

T(2)=3 ;
T(0)=1;
T(2*k-1)=0
T(2*k)=3*T(2*k-2)+2*(T(2*k-4)+T(2*k-6)+..+T(2) )

#include <stdio.h>

long T[31];

long t(int n)

{

int i;

if(n==2)return 3;

if(T[n]!=0)return T[n];

else

{

T[n]=3*t(n-2)+2;

for(i=n-4;i>=2;i=i-2)

T[n]+=2*t(i);

}

return T[n];

}

void main()

{

int input;

scanf("%d",&input);

while(input!=-1){

if(input%2==1)printf("0\n");

else if(input==0)printf("1\n");

else printf("%ld\n",t(input));

scanf("%d",&input);

}

posted on 2007-11-15 01:06 流牛ζ木马阅读(2227) 评论(2) 编辑收藏引用

# re: ACM PKU 2663 Tri Tiling 简单的动态规划有趣 2008-09-10 09:39 路过

#include <stdio.h>
long T[31];
long t(int n)
{
int i;
if(n==2)return 3;
if(T[n]!=0)return T[n];
else
{
T[n]=3*t(n-2)+2;
for(i=n-4;i>=2;i=i-2)
T[n]+=2*t(i);
}
这个怎么看不懂，if(T[n]!=0)return T[n]; 回复更多评论

# re: ACM PKU 2663 Tri Tiling 简单的动态规划有趣 2009-12-12 10:53 sleepycat

T(2*k)=3*T(2*k-2)+2*(T(2*k-4)+T(2*k-6)+..+T(2) )掉了
T（0）
应该是
T(2*k)=3*T(2*k-2)+2*(T(2*k-4)+T(2*k-6)+..+T(2) +T(0) ) 回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

# re: ACM PKU 2663 Tri Tiling 简单的动态规划有趣 2008-09-10 09:39 路过

# re: ACM PKU 2663 Tri Tiling 简单的动态规划有趣 2009-12-12 10:53 sleepycat