HDU4570----Multi-bit Trie----簡單的DP

題目意思：

給你N個數

要你分成多段，每段長度不能超過20

是的sum(ai*(2^bi))最小，ai為每段第一個數，bi為長度

解題思路：

設dp[i] = min(dp[i],dp[j]+a[i]*2^(j-i))，1<=i<=n，i+1<=j<=min(i+20,n+1)

dp[i]表示以第i個作為總的開頭的值

最後就dp[1]以及分成n段的一個比較

網上的代碼很多，我寫了一個迭代的，速度上要比記憶化搜索快一些

#include<cstdio>   
#include<cstring>   
#include<cmath>   
#include<algorithm>   
#include<iostream>   
using namespace std;  
  
#define ULL long long   
  
const int maxn = 65;  
  
ULL dp[maxn];  
ULL a[maxn];  
int n;  
  
int main()  
{  
    int t;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d",&n);  
        ULL ans=0;  
        for(int i=1;i<=n;i++)  
        {  
            cin>>a[i];  
            ans += a[i]*2;  
        }  
  
        dp[n] = a[n]*2;  
        dp[n+1] = 0;  
        for(int i=n-1;i>=1;i--)  
        {  
            dp[i] = (1ULL<<62-1);  
            for(int j=i+1;j<=min(i+20,n+1);j++)  
            {  
                dp[i] = min(dp[i],dp[j]+a[i]*(1<<(j-i)));  
            }  
        }  
  
        cout<<min(ans,dp[1])<<endl;  
    }  
    return 0;  
}