C题解--“歌尔创客杯”第二届哈尔滨理工大学（荣成）程序设计竞赛

C 花生米
简单dp，或者说，找规律。
dp[70]的时候有2073693258389777176，所以dp要用long long存，不然会炸。

先算几组，dp[1]=1,dp[2]=2,dp[3]=4,dp[4]=7,dp[5]=13......
得公式为dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

还是算不出这个公式的话，我可以再详细帮你们算一下。
dp[1]=1 [1]
dp[2]=2 [11,2]
dp[3]=4 [111,12,21,3]
dp[4]=7
[1111,112,121,13]，开头为1的时候为dp[3]=4
[211,22]，开头为2的时候为dp[2]=2
[31]，开头为3的时候为dp[1]=1
所以dp[4]=dp[3]+dp[2]+dp[1]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100];
void f(){
    dp[1]=1;
    dp[2]=2;
    dp[3]=4;
    for(int i=4;i<100;i++)
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
int main(){
    int n;
    f();
    scanf("%d",&n);
    while(n--){
        int m;
        scanf("%d",&m);
        printf("%lld\n",dp[m]);
    }
    return 0;
}