网站推广策略和效果评价,怎么加速网页,天猫网站建设的优势有哪些,南宁刚刚发生的事分离与合体
题目大意#xff1a;
有n个区域#xff0c;可以把它们分为两个区间#xff0c;结果加上左边区间的最左区域的数和最右区域的数还有右边区间的最右区域的数#xff0c;就这样不停分#xff0c;使结果最大#xff0c;并输出各分界线的位置#xff08;按1/2,2…分离与合体
题目大意
有n个区域可以把它们分为两个区间结果加上左边区间的最左区域的数和最右区域的数还有右边区间的最右区域的数就这样不停分使结果最大并输出各分界线的位置按1/2,2/4,4/8的顺序
原题
题目描述
经过在机房里数日的切磋LYD从杜神牛那里学会了分离与合体出关前杜神牛给了他一个测试… 杜神牛造了n个区域它们紧邻着排成了一行编号1~n。在这每个区域里都放着一把OI界的金钥匙每一把都有一定的价值LYD当然想得到它们了。然而杜神牛规定LYD不可以一下子把它们全部拿走而是每次只可以拿一个。为了尽快的拿到所有的金钥匙LYD自然就用上了刚学的分离与合体特技。 一开始LYD可以选择从1到n-1的任何一个区域(记为K)进入进入后LYD会在K区域发生分离从而分离为两个小LYD。分离完成的同时会有一面墙在K和K1区域之间升起从而把1到k和k1到n阻断为两个独立的区间。然后两个小LYD分别进入1到k和k1到n并在各自的区间内任选除了区间末尾区域以外(即1到k-1或k1到n-1)的任何一个区域再次发生分离就一共有了4个小小LYD……重复进行以上所叙述的分离直到每个小LYD发现自己所在的区间只剩下了一个区域他们就可以抱起自己梦寐以求的OI金钥匙。 但是LYD不能就这么分成n多个个体存在于世界上这些小LYD还会再合体合体的两个小LYD所在的区间中间的墙会消失。合体会获得一定的价值计算方法是(合并后所在区间的左右端区域里金钥匙的价值之和) 乘 (之前分离的时候所在区域的金钥匙价值)。 {例如LYD曾经在13区间中的2号区域分离成为12和3两个区间合并时获得的价值就是1号金钥匙价值3号价值*(2号金钥匙价值)。} LYD请你编程求出最终可以获得的总价值最大是多少。并按照分离阶段从前到后区域从左向右的顺序输出发生分离的区域编号 (例如先打印1分为2的分离区域然后从左到右打印2分为4的分离区域然后是4分为8的…) 。 注意若有多种方案选择分离区域尽量靠左的方案也可以理解为输出字典序最小的。
输入
第一行:正整数n (2n300) 第二行:n个正整数表示1~n区域里每把金钥匙的价值。 保证答案及运算过程中不超出longint范围。
输出
第一行一个数即获得的最大价值 第二行按照分离阶段从前到后区域从左向右的顺序输出发生分离的区域编号中间用一个空格隔开若有多种方案选择分离区域尽量靠左的方案也可以理解为输出字典序最小的。
输入样例
7
1 2 3 4 5 6 7输出样例
238
1 2 3 4 5 6说明
数据范围约定
对于%20的数据 N10 对于%40的数据 N50 对于%100的数据 N300 a[i]300
解题思路
石子合并改一下将加上的数改成题意然后递归输出分界线
代码
#includecstdio
#includeiostream
#includecstring
using namespace std;
int n,k,t,a[305],f[305][305],b[305][3055];
void dg(int x,int y,int dep)
{if (xy) return;//相交在一起了if (depk)//刚好{printf(%d ,b[x][y]);//输出t1;//记录return;}dg(x,b[x][y],dep1);//左边dg(b[x][y]1,y,dep1);//右边
}
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d,a[i]);for (int in-1;i0;--i)//石子合并模板for (int ji1;jn;j)for (int ci;cj;c)if(f[i][c]f[c1][j](a[i]a[j])*a[c]f[i][j])//想加的东西改成最左加最右乘上中间{f[i][j]f[i][c]f[c1][j](a[i]a[j])*a[c];b[i][j]c;//记录}printf(%d\n,f[1][n]);t1;while(t){t0;//判断是否有输出k;//分的每一层dg(1,n,1);}
}
