dp hdu-4570-Multi-bit Trie

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=4570
タイトル:
変換問題は、n個の数を与え、各セグメントの最初の数に2を乗じたセグメントの数次方の和が最小になるように分割することである.各セグメントの個数は20を超えない.
問題解決の考え方:
dp[i]は,i個の数が問題の要件を満たす区分の最小総和を表す.
dp[i]=Min(dp[i],sa[i-j+1]*bi[j]+dp[i-j]);
コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
#define Maxn 70
ll dp[Maxn],sa[Maxn];
int n;
int bi[25];

ll Min(ll a,ll b)
{
   return a<b?a:b;
}
int main()
{
   int t;

   bi[0]=1;
   for(int i=1;i<=20;i++)
      bi[i]=bi[i-1]*2;

   scanf("%d",&t);
   while(t--)
   {
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
         scanf("%I64d",&sa[i]);
      memset(dp,INF,sizeof(dp));
      dp[0]=0;
      for(int i=1;i<=n;i++)
      {
         /*if(i<=20)
            dp[i]=sa[1]*bi[i];*/
         //          
         for(int j=1;j<=20&&i>=j;j++) //   20 ，
         {
            dp[i]=Min(dp[i],sa[i-j+1]*bi[j]+dp[i-j]);
         }
      }
      printf("%I64d
",dp[n]);
   }
   return 0;
}