题目描述
经过在机房里数日的切磋,LYD从杜神牛那里学会了分离与合体,出关前,杜神牛给了他一个测试……
杜神牛造了n个区域,他们紧邻着排成一行,编号1..n。在每个区域里都放着一把OI界的金钥匙,每一把都有一定的价值,LYD当然想得到他们了。然而杜神牛规定LYD不能一下子把他们全部拿走,而是每次只可以拿一把。为了尽快得到所有金钥匙,LYD自然就用上了刚学的分离与合体特技。
一开始LYD可以选择1..n-1中的任何一个区域进入,我们不妨把这个区域记为k。进入后LYD会在k区域发生分离,从而分离成两个小LYD。分离完成的同时会有一面墙在k区域和k+1区域间升起,从而把1..k和k+1..n阻断成两个独立的区间,并在各自区间内任选除区间末尾之外(即从1..k-1和k+1..n-1中选取)的任意一个区域再次发生分离,这样就有了四个小小LYD……重复以上所叙述的分离,直到每个小LYD发现自己所在的区间只剩下了一个区域,那么他们就可以抱起自己梦寐以求的OI金钥匙。
但是LYD不能就分成这么多个个体存在于世界上,这些小LYD还会再合体,合体的小LYD所在区间中间的墙会消失。合体会获得(合并后所在区间左右端区域里金钥匙价值之和) \times()×(之前分离的时候所在区域的金钥匙价值)。
例如,LYD曾在1..3区间中的2号区域分离成为1..2和3..3两个区间,合并时获得的价值就是(1号金钥匙价值+3号金钥匙价值) \times()×(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阻断成两个独立的区间,并在各自区间内任选除区间末尾之外(即从1..k-1和k+1..n-1中选取)的任意一个区域再次发生分离,这样就有了四个小小LYD……重复以上所叙述的分离,直到每个小LYD发现自己所在的区间只剩下了一个区域,那么他们就可以抱起自己梦寐以求的OI金钥匙。
但是LYD不能就分成这么多个个体存在于世界上,这些小LYD还会再合体,合体的小LYD所在区间中间的墙会消失。合体会获得(合并后所在区间左右端区域里金钥匙价值之和) \times()×(之前分离的时候所在区域的金钥匙价值)。
例如,LYD曾在1..3区间中的2号区域分离成为1..2和3..3两个区间,合并时获得的价值就是(1号金钥匙价值+3号金钥匙价值) \times()×(2号金钥匙价值)。
LYD请你编程求出最终可以获得的最大总价值,并按照分离阶段从前到后,区域从左到右的顺序,输出发生分离区域编号。若有多种方案,选择分离区域尽量靠左的方案(也可以理解为输出字典序最小的)。
例如先打印一分为二的区域,然后从左到右打印二分为四的分离区域,然后是四分为八的……
输入描述:
第一行一个正整数n第二行n个用空格分开的正整数a_iai,表示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位正整数范围。
#include<bits/stdc++.h> using namespace std; const int N = 3e2 + 7; int a[N], dp[N][N], pre[N][N], n, l, r; pair<int, int> q[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int len = 2; len <= n; len++) { for (int l = 1; l <= n - len + 1; l++) { int r = l + len - 1; for (int k = l; k < r; k++) { int c = dp[l][k] + dp[k + 1][r] + (a[l] + a[r]) * a[k]; if (dp[l][r] < c) { dp[l][r] = c; pre[l][r] = k; } } } } cout << dp[1][n] << endl; q[r++] = make_pair(1, n); while (l < r) { pair<int, int> u = q[l++]; int k = pre[u.first][u.second]; cout << k << " "; if (u.first != k) { q[r++] = make_pair(u.first, k); } if (k + 1 != u.second) { q[r++] = make_pair(k + 1, u.second); } } return 0; }
原文链接: https://www.cnblogs.com/HighLights/p/13328612.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/367807
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!