贪心|[贪心] 矩形分割
| |
描述 Description |
|
|
| |
出于某些方面的需求，我们要把一块N×M的木板切成一个个1×1的小方块。 对于一块木板，我们只能从某条横线或者某条竖线（要在方格线上），而且这木板是不均匀的，从不同的线切割下去要花不同的代价。而且，对于一块木板，切割一次以后就被分割成两块，而且不能把这两块木板拼在一起然后一刀切成四块，只能两块分别再进行一次切割。 现在，给出从不同的线切割所要花的代价，求把整块木板分割成1×1块小方块所需要耗费的最小代价。 |
||
| |
|
|
|
| |
【贪心|[贪心] 矩形分割】 |
|
|
| |
输入格式 Input Format |
|
|
| |
输入文件第一行包括N和M，表示长N宽M的矩阵。 第二行包括N-1个非负整数，分别表示沿着N-1条横线切割的代价。 第二行包括M-1个非负整数，分别表示沿着M-1条竖线切割的代价。 |
||
| |
|
|
|
| |
|
|
|
| |
输出格式 Output Format |
|
|
| |
输出一个整数，表示最小代价。 |
||
| |
|
|
|
| |
|
|
|
| |
样例输入 Sample Input [复制数据] |
|
|
| |
2 2 3 3 |
||
| |
|
|
|
| |
|
|
|
| |
样例输出 Sample Output [复制数据] |
|
|
| |
9 |
||
| |
|
|
|
| |
|
|
|
| |
时间限制 Time Limitation |
|
|
| |
1s |
||
| |
|
|
|
| |
|
|
|
| |
注释 Hint |
|
|
| |
对于60%的数据，有1 ≤ N ,M≤ 100； 对于100%的数据，有1 ≤ N,M ≤ 2000。 |
||
开始以为是动态规划.想了想发现是贪心.
可以观察到切的刀数是固定的,n*m-1刀.
而且对于一个代价,越到后面切,代价越大.
自然想到应该使代价大的尽量早点切。
所以给代价排个序，标记一下横 纵
当我们想横着切一刀的时候{画一条穿过矩形的线}
代价为 竖着切的次数*代价
竖着切是横着切的次数*代价
所以给代价排个序，随便搞搞就没了。
第一个自己想出来的贪心。。。给输入坑了次。。
var n,m,i,ans,l,r:longint;
a,f:array[1..4000]of longint;
procedure qsort(l,r:longint);
var i,j,s,x:longint;
begin
i:=l;
j:=r;
x:=a[(l+r)div 2];
while i<=j do
begin
while a[i]>x do inc(i);
while a[j]推荐阅读
- 独自一人
- backtracing——|backtracing—— 131. 分割回文串
- 黄金分割
- (三)|(三) 贪心算法
- 实现tableViewCell分割线(全屏)
- Pytorch图像分割实践|Pytorch自定义层或者模型类
- 416.|416. 分割等和子集
- 刷题记录|【蓝桥必胜】试题 算法训练 kAc给糖果你吃-贪心排序
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- 416.分割等和子集