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   
#include   
#include   
#include   
#include   
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<