区间DP思路和题型总结

区间DP的总结和整理

基本思路

• 确定状态表示，即表示的状态是什么

• 确定划分依据，即的含义和取值（是否能取到L或者R）

• 基本框架（枚举区间长度和左端点，并确定右端点，通过k进行转移）

  for (int len = 2;len <= n;++len){
      for (int i = 1;i + len - 1 <= n;++i){
          int r = i + len - 1;int l = i;
          f[l][r] = INF;
          for (int k = l;k < r;++k)
              f[l][r] = min(f[l][r],f[l][k] + f[k+1][r] + s[r] - s[l-1]);
      }
  }
  cout << f[1][n] << endl;

基本题型

• 石子合并

• 环形石子合并

  将总区间扩展成两端（长度为2n），然后直接转化为线性的区间dp

  int a[N],s[N];
  int f[N][N],g[N][N];
  int n;
  int main(){
      cin >> n;
      for (int i = 1;i <= n;++i){
          cin >> a[i];
          a[i+n] = a[i];
      }
      for (int i = 1;i <= n*2;++i){
          s[i] = s[i-1] + a[i];
      }
  
      memset(f,0x3f,sizeof f);
      memset(g,-0x3f,sizeof g);
      for (int len = 1;len <= n * 2;++len){
          for (int i = 1;i + len - 1 <= n * 2;++i){
              int l = i,r =  i + len - 1;
              if (l == r)
                  f[l][r] = g[l][r] = 0;
              for (int k = l;k < r;++k){
                  f[l][r] = min(f[l][r],f[l][k] + f[k+1][r] + s[r] - s[l-1]);
                  g[l][r] = max(g[l][r],g[l][k] + g[k+1][r] + s[r] - s[l-1]);
              }
          }
      }
  
      int maxn = -INF,minn = INF;
      for (int i = 1;i <= n;++i){
          maxn = max(maxn,g[i][i+n-1]);
          minn = min(minn,f[i][i+n-1]);
      }
      cout << minn << endl << maxn << endl;
      return 0;
  }

• 能量项链（同上），注意k的取值和最后答案的选取

• 加分二叉树，这题比较特别，​选取的是数上所有的根节点，f[l][k-1]为左子树的得分，f[k+1][r]为右子树的得分，每次转移计算根节点的得分。

  void dfs(int l,int r){
      if (l > r) return;
      int root = g[l][r];
      cout << root << " ";
      dfs(l,root-1);
      dfs(root + 1,r);
  }
  
  int main(){
      cin >> n;
      for (int i = 1;i <= n;++i)   cin >> a[i];
  
      for (int len = 1;len <= n;++len){
          for (int l = 1;l + len - 1 <= n;++l){
              int r = l + len - 1;
              if (l == r){
                  g[l][r] = l;
                  f[l][r] = a[l];
              }
              else{
                  for (int k = l;k <= r;++k){
                      int left = k == l ? 1 : f[l][k-1];
                      int right = k == r ? 1 : f[k+1][r];
                      int s = left * right + a[k];
                      if (f[l][r] < s){
                          f[l][r] = s;
                          g[l][r] = k;
                      }
                  }
              }
          }
      }
      cout << f[1][n] << endl;
      dfs(1,n);
      puts("");
      return 0;
  }

• 凸多边形的划分（与能量项链类似，注意数据范围）

  inline __int128 read(){
      __int128 x = 0, f = 1;
      char ch = getchar();
      while(ch < '0' || ch > '9'){
          if(ch == '-')
              f = -1;
          ch = getchar();
      }
      while(ch >= '0' && ch <= '9'){
          x = x * 10 + ch - '0';
          ch = getchar();
      }
      return x * f;
  }
  inline void print(__int128 x){
      if(x < 0){
          putchar('-');
          x = -x;
      }
      if(x > 9)
          print(x / 10);
      putchar(x % 10 + '0');
  }
  
  int n;
  __int128 f[N][N];
  __int128 a[N];
  int main(){
      cin >> n;
      for (int i = 1;i <= n;++i)   a[i] = read();
  
      for (int len = 3;len <= n;++len){
          for (int l = 1;l + len - 1 <= n;++l){
              int r = l + len - 1;
              f[l][r] = INF;
              for (int k = l + 1;k < r;++k){
                  //if (a[l] * a[k] * a[r] < 0)    puts("yes");
                  f[l][r] = min(f[l][r],f[l][k] + f[k][r] + (a[l] * a[k] * a[r]));
              }
          }
      }
      print(f[1][n]);
      puts("");
      return 0;
  }

• 棋盘划分，二位的区间dp，区间的定义变为了矩形而不是线性的，参照二位前缀和的定义

  int n,m;
  double f[M][M][M][M][N];
  int s[N][N];
  double X;
  
  double get(int x1,int y1,int x2,int y2){
      double res = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1] - X;
      return res * res /  n;
  }
  
  double dp(int x1,int y1,int x2,int y2,int k){
      double &v = f[x1][x2][y1][y2][k];
      if (v >= 0)  return v;
      if (k == 1) return v = get(x1,y1,x2,y2);
  
      v = INF;
      for (int i = x1;i < x2;++i){
          v = min(v,dp(x1,y1,i,y2,k-1) + get(i+1,y1,x2,y2));
          v = min(v,dp(i+1,y1,x2,y2,k-1) + get(x1,y1,i,y2));
      }
  
      for (int j = y1;j < y2;++j){
          v = min(v,dp(x1,y1,x2,j,k-1) + get(x1,j + 1,x2,y2));
          v = min(v,dp(x1,j + 1,x2,y2,k-1) + get(x1,y1,x2,j));
      }
      return v;
  }
  
  int main(){
      cin >> n;
      for (int i = 1;i <= 8;++i){
          for (int j = 1;j <= 8;++j){
              cin >> s[i][j];
              s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
          }
      }
      X = (double) s[8][8] / n;
      memset(f,-1,sizeof f);
      printf("%.3lf\n",sqrt(dp(1,1,8,8,n)));
      return 0;
  }