AtCoder Grand Contest 035 D
发现操作后剩下的两个数一定是\(A_{1}\)和\(A_{n}\)。
同理，对于一段连续区间\([l,r]\)，一直进行题中操作，那么最后剩下的两个一定是\(A_{l}\)和\(A_{r}\)。
那么，每个数最终都会被加到\(A_{1}\)和\(A_{n}\)中，而且每个数可能会加到\(A_{1},A_{n}\)中多次，那么我们不妨设\(cnt_{i}\)表示\(A_{i}\)在最终的答案里加上了多少次。
最终的答案就可以表示为\(\sum_{i=1}^{n}A_{i}cnt_{i}\)。
这个也可以用来计算区间的贡献，具体的，\(dp(l,r,c1,c2)\)表示删除\((l,r)\)开区间，\(cnt(l)=c1,cnt(r)=c2\)时，最小贡献和。
转移时枚举\((l,r)\)中最后被删除的点\(i\)，则\(A_{i}\)会被加到\(A_{l}\)和\(A_{r}\)中各\(1\)次。根据状态定义，\(A_{l}\)会在答案中加上\(c1\)次，\(A_{r}\)会在答案中加上\(c2\)次，故\(i\)在答案中就会加上\((c1+c2)\)次，所以\(cnt(i)=c1+c2\)，对答案的贡献是\(A_{i}(c1+c2)\)。区间\((l,i)\)和\((i,r)\)中的数都在\(l,r,i\)之前删除了，且我们发现，\(i\)是\((l,i)\)的右端点，是\((i,r)\)的左端点，这样就形成了\(dp(l,i,c1,c1+c2)\)和\(dp(i,r,c1+c2,c2)\)两个子问题，就可以列出转移式如下：
\[dp_{l,r,c1,c2}=\min_{i=l+1}^{r} dp(l,i,c1,c1+c2)+dp(i,r,c1+c2,c2)+(c1+c2)A_{i} \]考虑\(n\)只有\(18\)，这个转移可以暴力搜索。
#include
using namespace std;
typedef long long ll;
const ll inf=1000000000000000000ll;
ll n,a[25];
ll dfs(int l,int r,ll cl,ll cr) {
if(l>r) return 0ll;
ll ans=inf;
for(int i=l;i<=r;i++)
ans=min(ans,dfs(l,i-1,cl,cl+cr)+dfs(i+1,r,cl+cr,cr)+a[i]*(cl+cr));
return ans;
}
int main(int argc,char **argv) {
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cout<