## What is DP on Interval?

DP on interval is an extension of linear dynamic programming. When dividing the problem in stages, it has a lot to do with the order in which the elements appear in the stage and which elements from the previous stage are merged.

Features of interval DP:

Merger : that is to integrate two or more parts, of course, it can also be reversed;

Features : able to decompose the problem into a form that can be combined in pairs;

Solution : Set the optimal value for the entire problem, enumerate the merge points, decompose the problem into two parts, and finally merge the optimal values of the two parts to get the optimal value of the original problem.

```
dp(i,j) = max(dp(i,j), dp(i,k) + dp(k+1,j) +cost)
```

## Interval DP Illustrated: Stone Merger

The piles of stones are discharged around the circular playground. Now the stones are to be combined into a pile in an orderly manner. It is stipulated that only two adjacent piles can be selected and merged into a new pile each time, and the number of stones in the new pile is recorded as the combined score.

Please write a program to read the heap count n and the number of stones in each pile, and calculate as follows:

Choose a scheme of merging stones (n-1 times) so that the sum of the combined scores is the largest. Choose a scheme of merging stones (n-1 times) so that the sum of sub-merged scores is the smallest.

Sample Input:

```
4
4 5 9 4
```

Sample Output:

```
43
54
```

### Solution

Since the question is a ring, we duplicate the array to make an array of size 2xn. Then we can just use normal linear array interval DP.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include<bits/stdc++.h>
using namespace std;
const int N = 420, INF = 0x3f3f3f3f;
int f[N][N];
int g[N][N];
int a[N];
int main()
{
int n;
cin >> n;
memset(f,INF,sizeof f);
memset(g,-INF,sizeof g);
for(int i = 1; i <= n; i ++ )
{
cin >> a[i];
a[i+n] = a[i];
}
//prefix sum and initialization
for(int i = 1; i <= 2 * n; i ++ )
{
a[i] += a[i-1];
g[i][i] = 0;
f[i][i] = 0;
}
//dp on interval: out loop is length, inner loop is the left bound
for(int len = 2 ; len <= n ;len ++ )
for(int l = 1; l + len - 1 <= 2 * n ; l ++ )
{
int r = l + len - 1;
for(int k = l - 1 ; k <= r; k ++ )
{
f[l][r] = min(f[l][r],f[l][k-1] + f[k][r] + a[r] - a[l - 1] );
g[l][r] = max(g[l][r],g[l][k-1] + g[k][r] + a[r] - a[l - 1] );
}
}
int minv = INF , maxv = -INF;
for(int i = 1; i <= n;i++)
{
minv = min(minv, f[i][i + n - 1]);
maxv = max(maxv, g[i][i + n - 1]);
}
cout << minv << endl << maxv << endl;
return 0;
}