P2220 [第五章习题1.2] 分离与合体
描述
【背景】
经过在机房里数日的切磋，LYD 从杜神牛那里学会了分离与合体，出关前，杜神牛给了 他一个测试...... 杜神牛造了 n 个区域，它们紧邻着排成了一行，编号 1~n。在这每个区域里都放着一把 OI 界的金钥匙，每一把都有一定的价值，LYD 当然想得到它们了。然而杜神牛规定 LYD 不可 以一下子把它们全部拿走，而是每次只可以拿一个。为了尽快的拿到所有的金钥匙，LYD 自 然就用上了刚学的分离与合体特技。
【问题描述】
一开始 LYD 可以选择从 1~n-1 的任何一个区域(记为 K)进入，进入后 LYD 会在 K 区域发 生分离，从而分离为两个小 LYD。分离完成的同时会有一面墙在 K 和 K+1 区域之间升起，从 而把 1~k 和 k+1~n 阻断为两个独立的区间。然后两个小 LYD 分别进入 1~k 和 k+1~n，并在各 自的区间内任选除了区间末尾区域以外(即 1~k-1 或 k+1~n-1)的任何一个区域再次发生分离， 就一共有了 4 个小小 LYD……重复进行以上所叙述的分离，直到每个小 LYD 发现自己所在的 区间只剩下了一个区域，他们就可以抱起自己梦寐以求的 OI 金钥匙。 但是 LYD 不能就这么分成 n 多个个体存在于世界上，这些小 LYD 还会再合体，合体的两 个小 LYD 所在的区间中间的墙会消失。合体会获得一定的价值，计算方法是：(合并后所在 区间的最左端区域和最右端区域里金钥匙的价值之和) 乘 (之前分离的时候所在区域的金 钥匙价值)。 {例如： 曾经在 1~3 区间中的 2 号区域分离成为 1~2 和 3 两个区间， LYD 合并时获得的价值就 是（1 号金钥匙价值+3 号价值）*(2 号金钥匙价值)。} LYD 请你编程求出最终可以获得的总价值最大是多少。并按照分离阶段从前到后，区域 从左向右的顺序，输出发生分离的区域编号 (例如：先打印 1 分为 2 的分离区域，然后从左 到右打印 2 分为 4 的分离区域，然后是 4 分为 8 的......) 。 注意： 若有多种方案， 选择分离区域尽量靠左的方案 （也可以理解为输出字典序最小的） 。
经过在机房里数日的切磋，LYD 从杜神牛那里学会了分离与合体，出关前，杜神牛给了 他一个测试...... 杜神牛造了 n 个区域，它们紧邻着排成了一行，编号 1~n。在这每个区域里都放着一把 OI 界的金钥匙，每一把都有一定的价值，LYD 当然想得到它们了。然而杜神牛规定 LYD 不可 以一下子把它们全部拿走，而是每次只可以拿一个。为了尽快的拿到所有的金钥匙，LYD 自 然就用上了刚学的分离与合体特技。
【问题描述】
一开始 LYD 可以选择从 1~n-1 的任何一个区域(记为 K)进入，进入后 LYD 会在 K 区域发 生分离，从而分离为两个小 LYD。分离完成的同时会有一面墙在 K 和 K+1 区域之间升起，从 而把 1~k 和 k+1~n 阻断为两个独立的区间。然后两个小 LYD 分别进入 1~k 和 k+1~n，并在各 自的区间内任选除了区间末尾区域以外(即 1~k-1 或 k+1~n-1)的任何一个区域再次发生分离， 就一共有了 4 个小小 LYD……重复进行以上所叙述的分离，直到每个小 LYD 发现自己所在的 区间只剩下了一个区域，他们就可以抱起自己梦寐以求的 OI 金钥匙。 但是 LYD 不能就这么分成 n 多个个体存在于世界上，这些小 LYD 还会再合体，合体的两 个小 LYD 所在的区间中间的墙会消失。合体会获得一定的价值，计算方法是：(合并后所在 区间的最左端区域和最右端区域里金钥匙的价值之和) 乘 (之前分离的时候所在区域的金 钥匙价值)。 {例如： 曾经在 1~3 区间中的 2 号区域分离成为 1~2 和 3 两个区间， LYD 合并时获得的价值就 是（1 号金钥匙价值+3 号价值）*(2 号金钥匙价值)。} LYD 请你编程求出最终可以获得的总价值最大是多少。并按照分离阶段从前到后，区域 从左向右的顺序，输出发生分离的区域编号 (例如：先打印 1 分为 2 的分离区域，然后从左 到右打印 2 分为 4 的分离区域，然后是 4 分为 8 的......) 。 注意： 若有多种方案， 选择分离区域尽量靠左的方案 （也可以理解为输出字典序最小的） 。
输入
第一行:正整数 n (2<=n<=300)
第二行:n 个正整数，表示 1~n 区域里每把金钥匙的价值。
保证答案及运算过程中不超出 longint 范围。
第二行:n 个正整数，表示 1~n 区域里每把金钥匙的价值。
保证答案及运算过程中不超出 longint 范围。
输出
第一行一个数，即获得的最大价值
第二行按照分离阶段从前到后，区域从左向右的顺序，输出发生分离的区域编号，中间 用一个空格隔开，若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序 最小的） 。
第二行按照分离阶段从前到后，区域从左向右的顺序，输出发生分离的区域编号，中间 用一个空格隔开，若有多种方案，选择分离区域尽量靠左的方案（也可以理解为输出字典序 最小的） 。
样例输入
7
1 2 3 4 5 6 7
样例输出
238 1 2 3 4 5 6
提示
对于 20%的数据 N<=10；
对于 40%的数据 N<=50；
对于 100%的数据 N<=300 a[i]<=300
对于 40%的数据 N<=50；
对于 100%的数据 N<=300 a[i]<=300
