回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...
/*---------------------------------------------------------------------------
File name: C76-45.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762
Modification history:
===========================================================================
Problem statement:
---------------------------------------------------------------------------
经典 76 道编程题 之 45:
45. (数列的最小代价) 给定一个正整数序列，例如：4,1,2,3, 不改变数的位置把
它们相加， 并且由括号来标记每一次加法所得到的和。例如：((4+1)+(2+3))=
((5)+(5))=10. 除去原数4、1、2、3之外，其余都为中间结果，如：5,5,10, 将中
间结果相加，得到：5+5+10=20, 数 20 称为此数列的一个代价。对于另一种算法:
(4+((1+2)+3))=(4+((3+3))=(4+(6))=10, 得到数列的另一个代价为：3+6+10=19.
若给出 N 个数的数列，求出此数列的最小代价。
Analysis:
---------------------------------------------------------------------------
The minimum sequence price (SMP) problem:
For n numbers a_1 ... a_n, we need to do n-1 additions, thus there are
n-1 intermediate results. Our goal is to make the sum of these n-1
intermediate results as small as possible.
Let P_{i..j} be the sub-problem for a_i ... a_j, 1<=i <=j <=n, and m[i, j]
the corresponding minimum price. Then
m[i, j] = 0, if i=j; (1)
= min_{i<=k<j} { m[i, k], m[k+1, j]} + (a_i + ... + a_j)
if i<j.
Note that the formula (1) is very similar to the matrix chain order problem
introduced on CLRS [2]'s book.
m[1, n] gives the minimum price for a_1 .... a_n. To track back where we should
put the parentheses, we use another matrix to keep record of the k which minimizes
the equation in (1).
Sample output:
---------------------------------------------------------------------------
Optimal solution is:
(4+((1+2)+3))
Minimum sequence price is 19.
Press any key to continue . . .
Optimal solution is:
(((((1+2)+3)+(4+5))+(6+7))+((8+9)+10))
Minimum sequence price is 173.
Press any key to continue . . .
Optimal solution is:
(((1+-2)+(9+-3))+10)
Minimum sequence price is 25.
Press any key to continue . . .
Reference:
---------------------------------------------------------------------------
1. 野比, [全民编程]76道高难度C++练习题
http://bbs.bc-cn.net/viewthread.php?tid=147967
2. CLRS, introduction to algorithms, 2nd ed, MIT press.
*/
#include <iostream>
using namespace std;
#define INFPos (~(1<<31))
#define DIM(a) sizeof( (a) ) / sizeof ( (a)[0] )
/** Implement formula (1).
O(n^3) time + O(n^2) space.
*/
int smp(int*a, int n);
/**
Print the optimal solutions (the parentheses) recursively.
*/
void printOptSoln(int**s, int*a, int i, int j);
template <class T>
T** new2dInit(int row, int col)
{
T** arr2d = new T*[row];
int i;
int j;
for(i=0; i<row; ++i)
{
arr2d[i] = new T[col];
}
for(i=0; i<row; ++i)
{
for(j=0; j<col; ++j)
{
arr2d[i][j] = T();
}
}
return arr2d;
}
template <class T>
void delete2d(T** arr2d, int row)
{
for(int i=0; i<row; ++i)
{
delete [] arr2d[i];
}
delete [] arr2d;
}
int main()
{
// test #1
int a[] = {4, 1, 2, 3};
smp(a, DIM(a));
// test #2
//int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//smp(a, DIM(a));
// test #3 --- numbers can be negative
//int a[] = {1, -2, 9, -3, 10};
//smp(a, DIM(a));
return 0;
}
int smp(int*a, int n)
{
int** m;
int** s;
int i;
int j;
int k;
int l; // length of a subproblem P_{i..j}
int q;
int sum; // a_i + ... + a_j
m = new2dInit<int>(n, n);
s = new2dInit<int>(n, n);
for (l=2; l<=n; ++l)
{
for (i=0; i<=n-l; ++i)
{
j = i+l-1;
// assign m[i,j] to be \+inf
m[i][j] = INFPos;
/**
This sum has been repeatedly calculated.
You could use another 2d buffer to store the
results. The situation is that we have two choices here:
choice #1: 3n^2 space + n^3 time (allocate a new 2d buffer for the sums)
choice #2: 2n^2 space + 2n^3 time.
As implemented, we are using choice #2.
*/
sum = 0;
for (k=i; k<=j; ++k)
{
sum += a[k];
}
for (k=i; k<j; ++k)
{
// implement (1)
q = m[i][k] + m[k+1][j] + sum;
if ( m[i][j] > q )
{
m[i][j] = q;
s[i][j] = k;
}
}
}
}
cout<<"Optimal solution is:\n";
printOptSoln(s, a, 0, n-1);
j = m[0][n-1]; // reuse j to keep m[0][n-1]
cout<<"\nMinimum sequence price is "<<j<<"."<<endl;
// free memory
delete2d<int>(m, n);
delete2d<int>(s, n);
return j;
}
void printOptSoln(int** s, int*a, int i, int j)
{
if(i==j)
{
cout<<a[i];
}
else
{
cout<<"(";
printOptSoln(s, a, i, s[i][j]); // i..k
cout<<"+";
printOptSoln(s, a, s[i][j]+1, j); // k+1..j
cout<<")";
}
}
７６道完整版有答案没？