TIOJ 1244 序列問題 Sequences [DP]

poao899    28K    4840MS    G++     0.36K     2010-03-31 02:50:18                                                    .






頗有趣的DP。




雷:





狀態存法   dp[n大小][該序列尾數]   但是這樣是10^8記憶體會爆炸

所以滾動。

另外是%100000007所以小心溢位。


轉移方式: dp[i-1][k]  + 結尾k or k+1    以及  開頭+1~k




//*******************************


#include<stdio.h>
#define MODE 100000007
int dp[10010], n, t;
long long tmp;
int main(){
    scanf("%d", &n);
    dp[1]= 1;
    for(int i=2; i<=n; i++){
        for(int j=i; j>0; j--){
            dp[j+1]+= dp[j];
            dp[j+1]%= MODE;
            tmp= (long long)dp[j]*j;
            dp[j]= (int)(tmp%MODE);
        }
    }
    for(int i=1; i<=n; i++){
        t+= dp[i];
        t%= MODE;
    }
    printf("%d\n", t);
}