xtu1303

xtu oj(:

Sequence

题目描述

n(1≤n≤60)个整数组成的序列(a1,a2,…,an),1≤ai≤8。
每次你可以从序列的头部或者尾部取一个数,第i(i=1,2,…,n)轮取数为ak,那么其代价为ak×2i−1。 求将序列取完的最小代价。

输入

第一行是一个整数T(1≤T≤1000),表示样例的个数。
每个样例的第一行是一个整数n,表示序列长度。第二行是n个整数ai,表示序列。

输出

每个样例输出一行。

样例输入

5
3
1 2 3
5
3 2 1 2 3
5
1 1 1 1 1
5
8 8 8 8 8
5
1 2 3 1 2

样例输出

11
49
31
248
48

思路

令dp[ i ][ j ]为闭区间[ i,j ]的方案数
那么dp[i][j]=min(dp[i+1][j]+2^step * a[i],dp[i][j-1]+2^setp * a[j])
递归即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e2+11;
ll f[maxn],a[maxn],dp[maxn][maxn];
ll n;
void init(){
f[0]=1;
for(ll i=1;i<=60;i++) f[i]=f[i-1]*2;
}
ll dfs(ll l,ll r,ll step){
if(l>r) return 0;
if(dp[l][r]) return dp[l][r];
return dp[l][r]=min(dfs(l,r-1,step+1)+f[step]*a[r],
dfs(l+1,r,step+1)+f[step]*a[l]);
}
void solve(){
cout<<dfs(1,n,0)<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
init();
ll ca;cin>>ca;
while(ca--){
memset(dp,0,sizeof(dp));
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
solve();
}
return 0;
}