学步园

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4570

题目意思：

给你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;
}