#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 55, INF = 0x3f3f3f3f; int d[N][N], c[N]; int dp (int i, int j) { if (d[i][j] < INF) return d[i][j]; for (int k = i+1; k < j; ++k) d[i][j] = min (d[i][j], dp (i, k) + dp (k , j) + c[j] - c[i]); return d[i][j]; } int main() { int l, n; while (scanf ("%d", &l), l) { scanf ("%d", &n); for (int i = 1; i <= n; ++i) scanf ("%d", &c[i]); c[++n] = l; memset (d, 0x3f, sizeof (d)); for (int i = 0; i <= n-1; ++i) d[i][i+1]=0; printf ("The minimum cutting is %d.\n", dp (0, n)); } return 0; }。该代码的含义是?
时间: 2023-06-23 18:08:56 浏览: 185
c++实现二叉查找树示例
这是一个求解钢条切割问题的动态规划算法。给定一根长度为L的钢条和一个长度数组C,要求将钢条切割成若干段,每段长度为C中的某个数,且要求切割次数最少。该算法使用了记忆化搜索的思想,将已经计算过的结果存储在数组d中,避免了重复计算。具体思路是,对于每个区间[i,j],枚举其中一个位置k,将其划分为两个子区间[i,k]和[k,j],然后递归地求解这两个子问题,并根据题目要求计算得到最小的切割次数。最终返回d[0][n],即整个钢条的最小切割次数。
阅读全文