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