题目大意:
给定一个长度为(N)的序列,每一次可以选择连续的三个数(a_{i-1}),(a_{i}),(a_{i+1}),将其合并变为(a_{i-1}+a_{i})和(a_{i},a_{i+1}),依次合并,最后只剩下两个数,求合并后这两个数的和的最小值。
输入格式:
(n)
(a_1) (a_2) (a_3) (a_4) (dots) (a_n)
思路分析
1. 猜测
刚拿到这道题的时候,我看了一下,发现不可做(哈哈哈)
但是我看了一下数据范围
然后通过计算器可以算出来
然后可以猜出,(2)的指数级别的可做。
2.分析猜测
我在上面为什么要写出2的指数,不是因为其他,就是因为在竞赛里面,这种看着(n)特别小的东西,一般时间复杂度都是指数级别的。
所以我们可以猜测时间复杂度的主流是(2^n)
3.分析题目
题目上描述的是将中间删去,再添加到两边去,那么我们可以考虑到说选两个点(l),(r),表示在l~r区间中最后留下来的是l&r。
题目上说的是将中间的删去,再添加到两边上去,那么我们可以想到正难则反的思想!
我们不考虑第一个删去的是谁,我们考虑最后一个留下的是谁。我们可以分析出为什么要这样想:
因为若是考虑第一个删去的是谁,那删去之后就还有许多不确定的抉择,很难分析,而且无法划分出区间,但是若考虑最后留下 的是谁,那我们就可以清楚的划分出区间,然后左右区间处理就对了。
区间!关键词!
那我们就自然而然想到区间DP
首先,操作可以看做是选择不是两边的一个数,将它删去并把它加到左右两项上
妨考虑倒序考虑整个过程,同时最后的结果一定是每个数乘上一个系数的和。那么最开始,(a_1)和(a_n)的系数都是1
那就可以考虑说设(dp[l][r][x][y])
表示当前未被删除的数两端是l和r,中间的数已经被删除过了。(a_l)对答案贡献的系数为(x),(a_r)对答案贡献的系数为(y)。
然后每次转移的时候就是贡献的转移
这样下来的话就是(O(n^3 imes 2^n))
可是我们完全可以将其改为搜索,然后(n^3)就没有了
#include<cstdio>
#include<iostream>
#define re register int
#define Starseven main
#define ll long long
using namespace std;
const int N=20;
ll a[N];
ll Dfs(int l,int r,int x,int y){
if(l+1>=r) return 0;
ll ans=100000000000000000;
for(re i=l+1;i<=r-1;i++)
ans=min(ans,Dfs(l,i,x,x+y)+Dfs(i,r,x+y,y)+a[i]*(x+y));
return ans;
}
int Starseven(void){
int n;
cin>>n;
for(re i=1;i<=n;i++) cin>>a[i];
cout<<a[1]+a[n]+Dfs(1,n,1,1)<<endl;
return 0;
}