杭电acm2517属什么类型题？

Question

找不着思路，请高手指点

Answer 1

DP动态规划
见刘汝佳黑书

考虑左上角坐标为(x1,y1)，右下角坐标为(x2,y2)的棋盘，设它把切割k次以后得到的k+1块矩形的总分平方和最小值为d[k,x1,y1,x2,y2]
状态转移: 沿着某横线切或者竖线切，然后选一块继续切, 如横着切的两类决策是
d[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2]
d[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]
其中x1<=a<=x2

状态d[k,x1,y1,x2,y2]
设m为棋盘边长，则状态数目为m4n，决策数目为O(m)
转移时间取决于计算s[x1,y1,x2,y2]的时间
预处理先用O(m2)时间算出左上角为(1,1)的所有矩阵元素和，这样状态转移时间就是O(1)，总的时间复杂度为O(m5n)

Answer 2

机电类