题目描述

经过在机房里数日的切磋，LYD 从杜神牛那里学会了分离与合体，出关前，杜神牛给了他一个测试……

杜神牛造了 个区域，他们紧邻着排成一行，编号 。在每个区域里都放着一把 OI 界的金钥匙，每一把都有一定的价值，LYD 当然想得到他们了。然而杜神牛规定 LYD 不能一下子把他们全部拿走，而是每次只可以拿一把。为了尽快得到所有金钥匙，LYD 自然就用上了刚学的分离与合体特技。

一开始 LYD 可以选择 中的任何一个区域进入，我们不妨把这个区域记为 。进入后 LYD 会在 区域发生分离，从而分离成两个小 LYD。分离完成的同时会有一面墙在 区域和 区域间升起，从而把 和 阻断成两个独立的区间，并在各自区间内任选除区间末尾之外（即从 和 中选取）的任意一个区域再次发生分离，这样就有了四个小小 LYD……重复以上所叙述的分离，直到每个小 LYD 发现自己所在的区间只剩下了一个区域，那么他们就可以抱起自己梦寐以求的 OI 金钥匙。

但是 LYD 不能就分成这么多个个体存在于世界上，这些小 LYD 还会再合体，合体的小 LYD 所在区间中间的墙会消失。合体会获得 合并后所在区间左右端区域里金钥匙价值之和之前分离的时候所在区域的金钥匙价值。

例如，LYD 曾在 区间中的 号区域分离成为 和 两个区间，合并时获得的价值就是 号金钥匙价值 号金钥匙价值 号金钥匙价值。

LYD 请你编程求出最终可以获得的最大总价值，并按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。

例如先打印一分为二的区域，然后从左到右打印二分为四的分离区域，然后是四分为八的……

输入

第一行一个正整数n（2≤n≤300）第二行为n个用空格分开的正整数，表示1～n区域里每把金钥匙的价值。保证运算过程及结果不超出int范围

输出

第一行的一个数，即获得的最大价值。第二行按照分离阶段从前到后，区域从左向右的顺序，输出发生分离的区域编号，中间用一个空格隔开，若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）

样例输入

7
1 2 3 4 5 6 7

样例输出

238
1 2 3 4 5 6

题目类型：区间dp+广搜

思路

按区间长度从小到大枚举所有区间 [ j , i ]，再枚举所有决策点 t∈[ j , i−1 ]，
dp 方程为：dp[j][t]=max(dp[j][t],(a[t]+a[j])*a[k]+ dp[j][k]+dp[k+1][t]);
然后用广搜思路求出路径：区间最优决策点在dp的时候记录一下就可以，输出可以用队列来实现，和bfs的过程类似。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100010;
int ans,a[1000],dp[1000][1000],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j+i-1<=n;j++)
        {
            int t=i+j-1;
            for(int k=j;k<t;k++)
            {
                dp[j][t]=max(dp[j][t],(a[t]+a[j])*a[k]+dp[j][k]+dp[k+1][t]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
    queue<int>q1,q2;
    q1.push(1);
    q2.push(n);
    while(q1.size())
    {
        int i=q1.front(),j=q2.front();
        q1.pop(),q2.pop();
        for(int k=i;k<j;k++)
        {
            if(dp[i][j]==(a[i]+a[j])*a[k]+dp[i][k]+dp[k+1][j])
            {
                printf("%d ",k);
                q1.push(i),q2.push(k);
                q1.push(k+1),q2.push(j);
                break;
            }
        }
    }
    return 0;
}