贪心思想求解

解题思路:由题知每次融合会消去一颗珠的尾标记和后一颗的头标记，将其一串珠子的首尾标记可抽象为一个数组后，也就是融合会消去抽象化数组的一个元素，也就是消去了一颗珠的尾标记和后一颗的头标记变成一颗珠，由于问题解具有最优子结构，寻找规律后发现每次融合所消去的数字得尽可能小，才能使结果最大化，满足贪心算法的思想
注意事项:

参考代码:

#include

#include

using namespace std;

void fun1(int** sz1,int N)

{

for (int i=N;i>=0;i--)

{

for(int j=0;j<i;j++)

if (sz1[0][j] > sz1[0][j + 1])

{

int asd = sz1[0][j + 1];

sz1[0][j+1] =sz1[0][j];

sz1[0][j] = asd;

asd = sz1[1][j + 1];

sz1[1][j + 1] = sz1[1][j];

sz1[1][j] = asd;

}

}

}

int main()

{

int N,Max=0;

cin >> N;

int* sz = new int[N];

int** bj = new int*[2];

    for (int i=0;i<N;i++)

{

cin >> sz[i];

if (sz[i] > Max)Max = sz[i];

}

for (int i=0;i<2;i++)

{

bj[i] = new int[N];

if (i == 0)

{

for(int j=0;j<N;j++)

bj[0][j] = sz[j];

}

else

{

for(int j=0;j<N;j++)

bj[1][j] = j;

}

}

bj[2] = new int[N];

fun1(bj, N-1);

long ans = 0;

for (int i1=0;i1<N-1;i1++)

{

int t1, t2=bj[1][i1], t3;

if (t2== 0)

t1 = N - 1;

else

t1 = t2-1;

if (t2 == N - 1)

t3 = 0;

else

t3 = t2+1;

for (;;)

{

if (sz[t1] > 0)

{

break;

}

if (t1 == 0)t1 = N - 1;

else t1--;

}

for (;;(++t3)%=N)

{

if (sz[t3] > 0)

{

break;

}

}

ans += sz[t1] * sz[t2] * sz[t3];

sz[t2] = 0;

}

cout<<ans;

}