#include <iostream> #include<cstring> using namespace std; int dp[1001][1001]; int num, len, t, a[1001]; int main() { while (1) { memset(dp,0,sizeof(dp)); cin >> len; if(len==0) break; cin >> num; for (int i = 1; i <= num; i++) { cin >> a[i]; } a[0] = 0; a[num + 1] = len; // 相邻两个点切割成本为0 dp[0][0] = 0; for (int i = 1; i <= num + 1; i++) { dp[i][i] = 0; dp[i - 1][i] = 0; } // 因为根据更新规则，i依赖于比它大的，j依赖于比它小的，所以i从大大小遍历，j从小到大 for (int i = num; i >= 0; i--) { for (int j = i + 2; j <= num + 1; j++) { // 如果i和j相等，那么只有一个切割点， dp[i][j] = 0x3f3f3f3f; // 遍历所有的分割点 for (int k = i + 1; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); } dp[i][j] += a[j] - a[i]; } } cout << "The minimum cutting is "<< dp[0][num + 1]<<".\n"; } return 0; }