FOJ 1319 Blocks of Stones[ 區間 ]

FOJ 1319 Blocks of Stones[ 區間 ]

Blocks of Stones

Description

There are n blocks of stones in a line laying on the ground. Now you are to merge these blocks of stones together with the restriction that you can only merge the neighbouring blocks each time. The score you get for each merging is the number of stones the new blocks has.

Before merging, you are allowed to swap a neighbouring block. You are to calculate the minimal score you will get during the merging process, and the swap position.

Input

There are multiple test cases. For each case, the first line contains a integer n(n<=100), representing the number of blocks. The second line contains n integers, representing number of stones in each blocks

Output

For each case, output 2 lines. The first line contains a single integer, representing the minimal score. The second line contains to integers in the form "(k,k+1)", representing the swap position. If there is more than one swap position which can be the minimal score, output the one with the largest k. You should note that : If swap is not needed output "(0,1)".

Sample Input

3
2 5 1
3
1 2 5

Sample Output

11(2,3)11(0,1)

思路：

階段：以歸並石子的長度為階段，一共有n-1個階段。
狀態：每個階段有多少堆石子要歸並，

當歸並長度為2時，有n-1個狀態；
當歸並長度為3時，有n-2個狀態；
當歸並長度為n時，有1個狀態。
決策：當歸並長度為2時，有1個決策；

當歸並長度為3時，有2個決策；
當歸並長度為n時，有n-1個決策。

代碼：

#include 
#include 
#include 

using namespace std;
const int INF = 1 << 30;
const int N = 205;

int dp[N][N];
int sum[N];
int a[N];

int getMinval(int a[],int n)
{
    for(int i=0;i 0 ? sum[i-1]:0);
            for(int k=i;k