(example of dynamic planning) stone merging

Great ideas for solving problems , I suggest you chew it if you have nothing to do .

Equipped with  NN  Pile stones in a row , Its number is  1,2,3,…,N1,2,3,…,N.

Every pile of stones has a certain quality , It can be described as an integer , Now we're going to put this  NN  The stones are combined into a pile .

Only two adjacent stacks can be merged at a time , The price of the merger is the sum of the masses of the two piles of stones , After merging, the stones adjacent to the two piles will be adjacent to the new pile , Because the order of selection is different when merging , The total cost of the merger is also different .

For example, there are  44  The heaps of stones are  1 3 5 2, We can merge first  1、21、2  Pile up , The cost is  44, obtain  4 5 2, Merge again  1,21,2  Pile up , The cost is  99, obtain  9 2 , And then merge to get  1111, The total cost is  4+9+11=244+9+11=24;

If the second step is to merge first  2,32,3  Pile up , The price is  77, obtain  4 7, The cost of the last merger is  1111, The total cost is  4+7+11=224+7+11=22.

The problem is ： Find a reasonable way , Minimize the total cost , The minimum cost of output .

Input format

Number one on the first line  NN  Represents the number of piles of stones  NN.

The second line  NN  Number , Represents the mass of each pile of stones ( Not more than  10001000).

Output format

Output an integer , The minimum cost .

Data range

1≤N≤3001≤N≤300

sample input ：

4
1 3 5 2

sample output ：

22

#include <bits/stdc++.h>
using namespace std;
const int N=310;
int n;
int s[N];
int f[N][N];
int main()
{

    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&s[i]);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+s[i];
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
             int l=i,r=i+len-1;
             f[l][r]=1e8;
             for(int k=l;k<=r-1;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
    printf("%d\n",f[1][n]);
}