P5149: 矩形分割-训练套题T1T1
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
1. 矩形分割[cut.pas/cut.c/cut.cpp]
【问题描述】
出于某些方面的需求，我们要把一块
N×
M的木板切成一个个
1×
1的小方块。
对于一块木板，我们只能从某条横线或者某条竖线（要在方格线上），而且这木板是不均匀的，从不同的线切割下去要花不同的代价。而且，对于一块木板，切割一次以后就被分割成两块，而且不能把这两块木板拼在一起然后一刀切成四块，只能两块分别再进行一次切割。
现在，给出从不同的线切割所要花的代价，求把整块木板分割成
1×
1块小方块所需要耗费的最小代价。
【输入数据】
输入文件第一行包括
N和
M，表示长
N宽
M的矩阵。
第二行包括
N-1个非负整数，分别表示沿着
N-1条横线切割的代价。
第二行包括
M-1个非负整数，分别表示沿着
M-1条竖线切割的代价。
【输出数据】
输出一个整数，表示最小代价。
【输入样例】
2 2
3
3
【输出样例】
9
【数据规模】
对于
60%的数据，有
1 ≤
N ,M≤ 100；
对于
100%的数据，有
1 ≤
N,M ≤ 2000。
【提示】
算法1：贪心
分析：每切一刀横刀，横的块数+1，则竖的每切一刀都要多算1的代价。
每切一刀竖刀，竖的块数+1，则横的每切一刀都要多算1的代价。
显然放在越前切的刀所需要的代价要少，而最终所有的刀都得被切到，将代价高的刀放在前面切自然更优。得到贪心算法，每次挑一条最大代价的分割线切下去。用队列实现。
1、分别将横切与竖切数据按从大到小的顺序形成有序队列；
2、设定双指针指向横竖队列队头；
3、比较两指针指向值，选择大的切，计算代价，下移指针；
4、直到某一队空为止，计算剩余的代价。
时间复杂度O(log(N))(贪心是线性时间，此复杂度为快排所需时间)。
算法2：DP
由于每条线必切，每切一条总是使块数加1，则将第I条横分割线和第J条横分割线上下对掉或将第I条竖分割线和第J条竖分割线上下对掉，是不会影响结果的。
将横分割线和竖分割线分别按大至小快排一遍。使得切刀按从左至右从上至下顺序。
记F[I,j]表示切了前I条横分割线，前J条横分割线的最小代价。
每横线切I刀，总共分为I+1块横块，每竖线切J刀，总共分为J+1块横块。则有
F[I,j]=min{F[i-1,j]+row[i]* (j+1),F[I,j-1]+line[j]*(i+1)}
row[i]与line[j]代表横竖切刀代价，最后答案即为F[n-1,m-1]。
时间复杂度是O(N^2)。