四、书本整理book．pas／c／cpp)问题描述小明的书架上放了许多书,为了使书架变得整洁,小明决定整理书架,他将所有书按高度大小排列,这样排了之后虽然整齐了许多,但小明发现,书本的

Question

四、书本整理book．pas／c／cpp)
【问题描述】
小明的书架上放了许多书,为了使书架
变得整洁,小明决定整理书架,他将所有书按
高度大小排列,这样排了之后虽然整齐了许
多,但小明发现,书本的宽度不同,导致书架
看上去还是有些凌乱.小明把这个凌乱值定
义为相邻两本书的宽度差的绝对值的和.
例如有4本书：
l×2
5×3
2×4
3×1
那么小明将其排列整齐后的顺序是：
l×2
2×4
3×l
5×3
凌乱值就是2+3+2=7.
于是小明决定拿掉其中的k本书,使凌
乱值最小,你能帮他求出这个最小值吗?
已知每本书的高度都不一样.
【问题输入】
第一行两个数字n和k,代表书总共有n
本,要求从中去掉k本.(1≤n≤100,1≤k

Answer 1

主要的难点应该是状态的表示,一维下标表示有后效性的话,可以试试二维
先排序
opt[i][j]表示保留第i本书,且在第1-- i -1本书中已拿去j本的最小凌乱值(这里是不考虑第i本书之后 的局部)
opt[i][j]opt[i -1][j]是不拿第i -1本书的情况
opt[i -2][j -1]减去拿去第i -1本书的获益 是拿了第i -1本书的情况