【区间DP】环形变线性

解题思路:

相比于线性，环形的不确定性在于n-1次合并的开始点在哪

线性：合并[1,n]

环形有n种合并方案

 4 5 9 4，5 9 4 4，9 4 4 5，4 4 5 9

将环形拉直，在线性后面再复制一组

变成 4 5 9 4 4 5 9 4

最小代价:min(f[i][i+n-1])

最大代价：max(g[i][i+n-1])

注意事项:

参考代码:

import java.io.*;
import java.util.*;
 
  public class Main{
      static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
      static PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out));
      public static void main(String[]args) throws IOException{
          int n=Integer.parseInt(br.readLine());
          int []arr=new int[2*n+1];
          long []sum=new long [2*n+1];
          long [][]f=new long[2*n+1][2*n+1];
          long [][]g=new long[2*n+1][2*n+1];
        for(int i=1;i<=2*n;i++){
            Arrays.fill(f[i],Long.MAX_VALUE);
            Arrays.fill(g[i],Long.MIN_VALUE);
        }
        String []s=br.readLine().split(" ");
          for(int i=1;i<=n;i++){
              arr[i]=Integer.parseInt(s[i-1]);
              arr[i+n]=arr[i];
          }
          for(int i=1;i<=2*n;i++){
            sum[i]=sum[i-1]+arr[i];
              f[i][i]=0;
              g[i][i]=0; 
          }
          
          
          for(int len=2;len<=n;len++){
              for(int l=1;l+len-1<=2*n;l++){
                  int r=len+l-1;
                  for(int k=l;k<r;k++){
                      f[l][r]=Math.min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
                      g[l][r]=Math.max(g[l][r],g[l][k]+g[k+1][r]+sum[r]-sum[l-1]);                  
                      }
              }
          }
          long min=Long.MAX_VALUE;
          long max=Long.MIN_VALUE;
          for(int i=1;i<=n;i++){
              min=Math.min(min,f[i][i+n-1]);
              max=Math.max(max,g[i][i+n-1]);
          }
          pw.println(min);
          pw.println(max);
          pw.flush();
      }
  }