整理的算法模板合集： ACM模板
本题其实就是一个区间DP 的模板题，总长度为len，有n个切割点，也就是说能被切割成n+1段，所以左边界是0，有边界是n + 1，所以答案就是f[0][n + 1]。 其中我们要把两个端点设为：a[0] = 0，a[n + 1] = len
边界：f[i][i] = f[i][i + 1] = 0;（不然没办法转移，因为要从他们开始+）
转移方程： f [ i ] [ j ] = m i n { f [ i ] [ k ] + f [ k ] [ j ] } + a [ j ] − a [ i ] f[i][j] = min\{f[i][k]+ f[k][j]\} + a[j] - a[i] f[i][j]=min{f[i][k]+f[k][j]}+a[j]−a[i]
注意根据题意，我们长度至少为2的时候（也就是有三个点）才能在中间的点将他们切开。
总时间复杂度为 O ( n 3 ) O(n^3) O(n3)
紫书上说使用四边形不等式优化可以优化到 O ( n 2 ) O(n^2) O(n2)，这个有缘再学。
#include<cstdio> #include<cmath> #include<algorithm> #include<iostream> #include<cstring> using namespace std; typedef long long ll; const int N = 507, M = 5000007, INF = 0x3f3f3f3f; const double eps = 1e-6; int n, m; int f[N][N]; int len; int a[N]; int main() { while(scanf("%d", &len) != EOF && len){ scanf("%d", &n); memset(f, 0x3f, sizeof f); for(int i = 1; i <= n; ++ i){ scanf("%d", &a[i]); f[i][i] = f[i][i + 1] = 0; } //0是左端点n + 1是右端点 a[n + 1] = len;//n个点分成n+1段 for(int length = 2; length <= n + 1; ++ length){//从0开始0,1,2,这样才能在1点切开,0是左端点不是切割点 for(int i = 0; i <= n - length + 1; ++ i){ int j = i + length; int minv = INF; for(int k = i + 1; k < j; ++ k){ minv = min(minv, f[i][k] + f[k][j]); } f[i][j] = minv + a[j] - a[i]; } } printf("The minimum cutting is %d.\n", f[0][n + 1]); } return 0; }