首页 > 代码库 > hdu4570

hdu4570

 1 #include <iostream> 2 #define N 65 3 using namespace std; 4  5 const long long INF = 1LL<<50; 6 long long dp[N][N],a[N]; 7  8 int main() 9 {10     int _;11     cin>>_;12     while(_--)13     {14         int n,i,j,k;15         cin>>n;16         for(i=0;i<n;i++)    cin>>a[i];17         for(i=0;i<n;i++)18             for(j=i;j<n;j++)19                 if(j-i<20)  dp[i][j]=a[i]*(1<<(j-i+1));20                 else        dp[i][j]=INF;21         for(i=n-1;i>=0;i--)22             for(j=n-1;j>=i;j--)23                 for(k=i;k<j;k++)24                     dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);25         cout<<dp[0][n-1]<<endl;26     }27     return 0;28 }