題目大意：從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 閱讀(397)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數學/數論