#2049. 切蛋糕 Cake slicing
切蛋糕 Cake slicing
题目描述
有一个 行 列()的网络蛋糕上有 个樱桃。每次可以用一刀沿着网络线把蛋糕切成两块,并且只能够直切不能拐弯。要求最后每一块蛋糕上恰好有一个樱桃,且切割线总长度最小。求出这个最小总长度。
输入格式
有多组测试数据。
对于每组数据,第一行三个整数 。
接下来 行每行两个整数 描述第 个樱桃所在位置。
输出格式
对于每组数据,输出一行 Case x: y,其中 表示当前是第 组测试数据, 表示答案即切割线最小总长度。
样例
3 4 3
1 2
2 3
3 2
Case 1: 5
题目来源:洛谷 UVA1629