OJ題目:click here~~
題目分析:四塔問題,n個盤,從塔1,到塔4,至少需要多少步。
這裡n的范圍是( 0 , 50000 ] ,所以不能直接用四塔算法。這裡找規律就可以了。
AC_CODE
const int mod = 10000; const int Max_N = 50002; int dp[Max_N]; int main() { int i , j = 0, k = 2, t = 2; dp[1] = 1; for(i = 2;i <= Max_N-2;i++){ j++; dp[i] = (dp[i - 1] + t) % mod; if(j == k){ j = 0; k++; t *= 2; t %= mod; } } int n; while(scanf("%d",&n) != EOF) cout << dp[n] << endl; return 0; }