# [题解] hihocoder – 1365 图片排版

## 问题描述

0123456789
----------
111
111  333
11122333
11122333


0123456789
----------
44
111     44
111  33344
1112233344
1112233344


0123456789
----------
44
111     44
111  33344
1112233344
1112233344
5555555555
66666
66666777
66666777
66666777
66666777


## 样例输入

4 3
2 2
2 3
2 2


## 样例输出

2


## 解题思路

$$sum[x] = h + sum[v]$$

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 100000 + 10;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9')
ch = getchar();

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

int m, n;
int w[MAXN], h[MAXN];
int pre_h[MAXN], line[MAXN], End[MAXN];
int sum[MAXN];

inline int calc(int a, int b, int c){
return ceil((long double) (a * c) / b);
}

int main(){

for(register int i=1; i<=n; i++){
}

int tmp_n = 1;
int rest = m;
int high = 0;
int now = 1;

while(true){
if(now > n){
break;
}
if(rest >= w[now]){
line[now] = tmp_n;
high = max(high, h[now]);
rest -= w[now];
now++;
}else if(rest == 0){
End[tmp_n] = now-1;
pre_h[tmp_n] = pre_h[tmp_n - 1] + high;
high = 0;
rest = m;
tmp_n++;
}else{
line[now] = tmp_n;
high = max(high, calc(h[now], w[now], rest));
rest = 0;
now++;
}
}

for(register int i=n; i>=1; i--){
rest = m;
now = i;
high = 0;

while(true){
if(now > n)
break;

if(rest >= w[now]){
high = max(high, h[now]);
rest -= w[now];
now++;
}else if(rest == 0){
break;
}else{
high = max(high, calc(h[now], w[now], rest));
rest = 0;
now++;
}
}

sum[i] = high + sum[now];
}

int ans = 0x3f3f3f3f;
int tmp = 0;

for(register int i=1; i<=n; i++){
tmp = 0;

int delete_line = line[i] - 1;
tmp += pre_h[delete_line];

rest = m;
high = 0;
now = End[delete_line] + 1;

while(true){
if(now > n)
break;

if(now == i){
now++;
continue;
}

if(rest >= w[now]){
high = max(high, h[now]);
rest -= w[now];
now++;
}else if(rest == 0){
break;
}else{
high = max(high, calc(h[now], w[now], rest));
rest = 0;
now++;
}
}

tmp += high;
tmp += sum[now];
ans = min(ans, tmp);
}

printf("%d", ans);
return 0;
}