Magicpig and Kinfkong come to like playing cards recently. Magicpig knows that Kinfkong is very good at mathematics, so he often asks Kinfkong

some very hard problems in order to baffle him. You know, Kinfkong is very clever, so he can defeat Magicpig each time. One day, Magicpig takes out a pile of n cards and asks Kinfkong a question: "Now I have n cards in my hand. We do't care about the face value of the cards, so we consider them to be the same. Now you can take some cards from my hand. Each time you can take 1,2 or 3 cards. Repeat this step until there is no more card in my hand. Now I want to know how many different ways can you take away all the cards from my hand. I give you 10 minutes. If you can't figure out the answer, you are defeated." You are a friend of Kinfkong. Now Kinfkong can not figure out the answer and there is no time left! He knows you are an excellent ACMer, so he needs you help!

输入格式

The input contains one or more data sets. Each data set consists of a positive integer n(<=500), denoting the number of cards.

A line which contains a single 0 will end the input.

输出格式

One number on each line, the number of distinct ways to take away all the cards in Magicpig's hand.

样例输入

1 2 3 0

样例输出

1 2 4

很简单的DP dp[i] = dp[i-1] + dp[i-2] +dp[i-3] , 要写高精 。

#include<iostream> #include <cstring> using namespace std; /*int main(){ unsigned long long dp[505]; int i,n; dp[1]=1;dp[2]=2;dp[3]=4; for(i=4;i<=500;i++){ dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } while(cin>>n&&n!=0){ cout<<dp[n]<<endl; } return 0; }*/ string Sum(string a,string b) { if(a.length()<b.length()) { string temp=a; a=b; b=temp; } int i,j; for(i=a.length()-1,j=b.length()-1;i>=0;i--,j--) { a[i]=(a[i]+(j>=0?b[j]-'0':0)); if(a[i]>'9') { a[i] -=10; if(i) a[i-1]++; else a='1'+a; } } return a; } int main() { string a[501]; a[1]="1"; a[2]="2"; a[3]="4"; int n,i; for(i=4;i<=500;i++) { a[i]=Sum(a[i-1],a[i-2]); a[i]=Sum(a[i],a[i-3]); } while(cin>>n && n) cout<<a[n]<<endl; return 0; }