区间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; }
