2013年8月14日 星期三

2013/8/14 TIOJ 1357 河內之塔-金色巨塔

// http://218.210.35.237:8080/JudgeOnline/showproblem?problem_id=1357
#include <iostream>
#include <cstdio>
using namespace std;
long long int dp[51]; long long int s[51];
int main()
{
    dp[0] = 0;
    s[0] = 1;
    for(int i = 1; i <= 50; i++) s[i] = s[i-1]*2;
    for(int i = 1; i <= 50; i++)
    {
        dp[i] = dp[0] + s[i]-1;
        for(int j = 1;  j < i; j++)
            dp[i] = min( dp[i], dp[j]*2+s[i-j]-1);
    }


    int t; scanf("%d", &t);
    while( t-- )
    {
       int n; scanf("%d", &n);
        printf("%I64d\n", dp[n]);
    }
}

沒有留言:

張貼留言