题目大意：从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 阅读(373)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数学/数论