LOJ10151 分离与合体

题意

一个序列 $S$ ，合并两个区间 $[l,x]$ 和 $[x,r]$ 对答案的贡献为 $(S_l+S_r)\times S_x$ 。先任取 $mid$ 将序列不断二分，直到每个区间只有一个元素后再合并。

求答案的最大值，以及每阶段二分时取的 $mid$ 。按照阶段从小到大，每阶段内从左到右输出。

其中序列的长度 $N\le 300$ 。

题解

显然区间dp，就是输出二分的方法有点麻烦。

我最开始是在记搜过程中记录在 $[l,r]$ 中最优为 $pos[l][r]$ ，然后不断递归输出。但很显然这样不能保证每阶段从左到右。

去看其他人的提交记录才发现可以对每个最优解同时记录深度，最后按照题意排序输出就行了。

#include<bits/stdc++.h>
#define mp make_pair
#define pr pair<int,int>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,cnt,s[305],f[305][305],pos[305][305];
pr ans[305];

int dfs(int l,int r)
{
    int &ans=f[l][r];
    if (l==r) return 0;
    if (ans) return ans;
    for (int i=l;i<r;i++) 
    {
        int now=dfs(l,i)+dfs(i+1,r)+s[i]*(s[l]+s[r]);
        if (now>ans)
        {
            ans=now;
            pos[l][r]=i;
        }
    }
    return ans;
}

void get_pos(int l,int r,int dep)
{
    if (l==r) return;
    ans[++cnt]=mp(dep,pos[l][r]);
    get_pos(l,pos[l][r],dep+1);
    get_pos(pos[l][r]+1,r,dep+1);
}

inline bool cmp(pr x,pr y) { return (x.first==y.first) ? x.second<y.second : x.first<y.first; }

int main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    printf("%d\n",dfs(1,n));
    get_pos(1,n,1);
    sort(ans+1,ans+cnt+1,cmp);
    for (int i=1;i<=cnt;i++) printf("%d ",ans[i].second);
    return 0;
}