题目大意:从1..n中选出若干个数字,要求满足两个条件:这些数字互不相临;在不违背第一个条件的情况下,不能再这些数字组成的集合中加入新的数字。
简单分析即可得到思路:1或2必选其一;假设上一次选择的是k,那么下一次要么选择k+2,要么选择k+3,否则就能够加入新的数字;得到一个解的条件是(k==n||k+1==n)。如此一来,只要在递归中加入记忆化即可。
以下是我的代码:
#include<stdio.h>
#include<string.h>
long n,d[87];
long dp(long now)
{
if(d[now]!=-1) return d[now];
d[now]=0;
if(now==n||now+1==n)
d[now]=1;
else
d[now]=dp(now+2)+dp(now+3);
return d[now];
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%ld",&n)==1)
{
memset(d,-1,sizeof(d));
printf("%ld\n",(n>=2?dp(1)+dp(2):dp(1)));
}
return 0;
}
posted on 2010-02-08 11:08
lee1r 阅读(377)
评论(0) 编辑 收藏 引用 所属分类:
题目分类:数学/数论