1573：分离与合体
时间限制: 1000 ms 内存限制: 524288 KB
题目描述
经过在机房里数日的切磋，LYD 从杜神牛那里学会了分离与合体，出关前，杜神牛给了他一个测试……
杜神牛造了 n 个区域，他们紧邻着排成一行，编号 1..n。在每个区域里都放着一把 OI 界的金钥匙，每一把都有一定的价值，LYD 当然想得到他们了。然而杜神牛规定 LYD 不能一下子把他们全部拿走，而是每次只可以拿一把。为了尽快得到所有金钥匙，LYD 自然就用上了刚学的分离与合体特技。
一开始 LYD 可以选择 1..n-1 中的任何一个区域进入，我们不妨把这个区域记为 kk。进入后 LYD 会在 k 区域发生分离，从而分离成两个小 LYD。分离完成的同时会有一面墙在k区域和 k+1 区域间升起，从而把 1..k 和 k+1..n 阻断成两个独立的区间，并在各自区间内任选除区间末尾之外（即从 1..k−1 和 k+1..n−1中选取）的任意一个区域再次发生分离，这样就有了四个小小 LYD……重复以上所叙述的分离，直到每个小 LYD 发现自己所在的区间只剩下了一个区域，那么他们就可以抱起自己梦寐以求的 OI 金钥匙。
但是 LYD 不能就分成这么多个个体存在于世界上，这些小 LYD 还会再合体，合体的小 LYD 所在区间中间的墙会消失。合体会获得 ((合并后所在区间左右端区域里金钥匙价值之和)×(之前分离的时候所在区域的金钥匙价值))。
例如，LYD 曾在 1..3 区间中的 2 号区域分离成为 1..2 和 3..3 两个区间，合并时获得的价值就是 (( 1 号金钥匙价值 +3 号金钥匙价值)×( 2 号金钥匙价值))。
LYD 请你编程求出最终可以获得的最大总价值，并按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。
例如先打印一分为二的区域，然后从左到右打印二分为四的分离区域，然后是四分为八的……
输入格式
第一行一个正整数 n 第二行 nn 个用空格分开的正整数 ai ，表示 1..n 区域里每把金钥匙的价值。
输出格式
第一行一个数，表示获得的最大价值
第二行按照分离阶段从前到后，区域从左到右的顺序，输出发生分离区域编号。若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序最小的）。
样例
样例输入
7
1 2 3 4 5 6 7样例输出
238
1 2 3 4 5 6数据范围与提示
对于 20% 的数据，n≤10；
对于 40% 的数据，n≤50；
对于 100% 的数据，n,ai≤300，保证运算过程和结果不超过 32 位正整数范围。
sol：这题面好多废话，其实不难，但是输出方案时不是dfs一样递归输出，要想bfs一样
#include <bits/stdc++.h> using namespace std; const int N=305; int n,a[N]; int dp[N][N],dp_Road[N][N]; struct Record { int l,r,Road; }; inline void Output() { register queue<Record>Queue; Queue.push((Record){1,n,dp_Road[1][n]}); while(!Queue.empty()) { Record tmp=Queue.front(); Queue.pop(); printf("%d ",tmp.Road); if(tmp.Road>tmp.l) Queue.push((Record){tmp.l,tmp.Road,dp_Road[tmp.l][tmp.Road]}); if(tmp.Road+1<tmp.r) Queue.push((Record){tmp.Road+1,tmp.r,dp_Road[tmp.Road+1][tmp.r]}); } return; } int main() { // freopen("separation3.in","r",stdin); // freopen("my.out","w",stdout); int i,j,k; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=2;i<=n;i++) { for(j=1;j+i-1<=n;j++) { int l=j,r=j+i-1; for(k=l;k<r;k++) if(dp[l][k]+dp[k+1][r]+(a[l]+a[r])*a[k]>dp[l][r]) { dp[l][r]=dp[l][k]+dp[k+1][r]+(a[l]+a[r])*a[k]; dp_Road[l][r]=k; } } } printf("%d ",dp[1][n]); Output(); return 0; } /* input 7 1 2 3 4 5 6 7 output 238 1 2 3 4 5 6 */