5 (optional) gene splicing (100 points)
Gene splicing is the joining of different DNA fragments. The existing n DNA fragments line up from left to right. Each time two adjacent DNA fragments were selected and stitched into a longer DNA fragment. The last DNA fragment was adjacent to the first. Repeat this process until all the DNA fragments form a single DNA fragment. The cost of each splicing is the sum of the lengths of the two selected DNA fragments. Now you want to know what the minimum and maximum costs of splicing these genes are, respectively.

Input format:
The first line, an integer n, represents the number of DNA fragments, 1 < n < 200.

Line 2, n integers Li, separated by spaces, Li represents the length of the first DNA fragment, 1 < Pi < 100, 1 < i < n.

Output format:
1 line, two integers, separated by spaces, representing the minimum and maximum costs required.

Input sample:
Here is a set of inputs. For example:

3
1 3 2
Output sample:
The corresponding output is given here. For example:

9 11

I am ashamed to say that I have always thought this topic was a greedy one. What seems obvious is that there is no way to prove greed at all. My first thought was to decide which was the smallest, which merge to take, which was the largest, and finally the smallest and largest. Analyzing the reason for the deviation of my thinking in that direction probably lies in me. At first glance, I think this topic is a kind of topic like "Merging fruits". Think you know the essence of the topic?
But after consulting other big guys, you know this is an interval DP problem.
Setting a dp[i][j] to represent the minimum or maximum cost of an interval, and then having learned a good technique, you can simulate all rings by changing the sequence 1 2 3 4 5 to 1 2 3 4 5 1 2 3 4. Avoid processing of very complex rings. Then, the code doesn't succeed all at once because the recursive relationships aren't written correctly.
The correct recursive relationship is as follows:
s u m sum Sum means prefix and sum, so now it seems that I suddenly find my code is not well written. Here is the first version of the code. I want to update a second version.
D P [ i ] [ j ] = m a x i ≤ k < j    { D P [ i ] [ k ] + D P [ k + 1 ] [ j ] + s u m [ j ] − s u m [ i − 1 ] } DP[i][j]=max_{i\leq k< j \,\,}\{DP[i][k]+DP[k+1][j]+sum[j]-sum[i-1]\} DP[i][j]=maxi≤k<j​{DP[i][k]+DP[k+1][j]+sum[j]−sum[i−1]}

#include<bits/stdc++.h>
using namespace std;
int f[410][410];
int input[1000];
int sum[210];
int n;
int main(){
    scanf("%d",&n);
    if(n==1){
        scanf("%d",&n);
        printf("0 0");
        return 0;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&input[i]);
    for(int j=n+1;j<=2*n-1;j++)
        input[j]=input[j-n];
    for(int i=1;i<=2*n-1;i++)
        sum[i]=sum[i-1]+input[i];
    for(int i=2*n-1;i>=1;i--)
    {
        f[i][i]=input[i];
        for(int j=i+1;j<=i+n-1&&j<=2*n-1;j++)
        {
            if(j==i+1)
            {
                f[i][j] =sum[j]-sum[i-1];
            }
            else
            {
                int Min=INT_MAX;
                for(int k = i; k < j; k++)
                {
                    int temp_Min=sum[j]-sum[i-1];
                    if(i!=k) temp_Min+=f[i][k];
                    if((k+1)!=j) temp_Min+=f[k+1][j];
                    Min = min(Min,temp_Min);
                }
                f[i][j] = Min;
            }
        }
    }
    int Min=INT_MAX;
    for(int i=1;i<=n;i++){
        Min=min(Min, f[i][i+n-1]);
    }
    printf("%d ",Min);

    for(int i=2*n-1;i>=0;i--)
    {
        f[i][i] = input[i];
        for (int j=i+1;j<=2*n-2;j++)
        {
            if(j==i+1)
            {
                f[i][j] =sum[j]-sum[i-1];
            }
            else
            {
                int Max=INT_MIN;
                for(int k = i; k < j; k++)
                {
                    int temp_Max=sum[j]-sum[i-1];
                    if(i!=k) temp_Max+=f[i][k];
                    if((k+1)!=j) temp_Max+=f[k+1][j];
                    Max = max(Max, temp_Max);
                }
                f[i][j] = Max;
            }
        }
    }
    int Max=INT_MIN;
    for(int i=1;i<=n;i++){
        Max=max(Max, f[i][i+n-1]);
    }
    printf("%d",Max);
    return 0;
}

The second version of the code comes out:
The only thing that has changed before is whether this f[i][i] is equal to or should actually be 0, so that either the special judgment can be removed or the question can't be understood properly by oneself, and the problem has only been discovered now. Rethinking is still very useful (think. jpg).
emmm actually has this type of Title I've done, LeetCode is called a strange printer
https://leetcode-cn.com/problems/strange-printer/
Unfortunately, they can't be integrated. This is a hard injury. There seems to be a lot to explore in this type of topic. So it's still a long way off.

#include<bits/stdc++.h>
using namespace std;
int f[410][410];
int input[1000];
int sum[210];
int n;
int main(){
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        scanf("%d",&input[i]);
    for(int j=n+1;j<=2*n-1;j++)
        input[j]=input[j-n];
    for(int i=1;i<=2*n-1;i++)
        sum[i]=sum[i-1]+input[i];

    for(int i=2*n-1;i>=1;i--)
    {
        for(int j=i+1;j<=i+n-1&&j<=2*n-1;j++)
        {
            if(j==i+1)
                f[i][j] =sum[j]-sum[i-1];
            else
            {
                int Min=INT_MAX;
                for(int k = i; k < j; k++)
                {
                    int temp_Min=f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
                    Min = min(Min,temp_Min);
                }
                f[i][j] = Min;
            }
        }
    }
    int Min=INT_MAX;
    for(int i=1;i<=n;i++)
        Min=min(Min, f[i][i+n-1]);
    printf("%d ",Min);
    for(int i=2*n-1;i>=0;i--)
    {
        for (int j=i+1;j<=2*n-2;j++)
        {
            if(j==i+1)
                f[i][j] =sum[j]-sum[i-1];
            else
            {
                int Max=INT_MIN;
                for(int k = i; k < j; k++)
                {
                    int temp_Max=f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
                    Max = max(Max, temp_Max);
                }
                f[i][j] = Max;
            }
        }
    }
    int Max=INT_MIN;
    for(int i=1;i<=n;i++)
        Max=max(Max, f[i][i+n-1]);
    printf("%d",Max);
    return 0;
}