图形排版

Posted on | Edited on | In | Views:

题意

小明需要在一篇文档中加入 N 张图片，其中第 i 张图片的宽度是 Wi，高度是 Hi。假设纸张的宽度是 M，小明使用的文档编辑工具会用以下方式对图片进行自动排版：

  1. 该工具会按照图片顺序，在宽度 M 以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。例如在 M=10 的纸张上依次打印 3x4, 2x2, 3x3 三张图片，则效果如下图所示，这一行高度为4。(分割线以上为列标尺，分割线以下为排版区域；数字组成的矩形为第x张图片占用的版面)
    img

  2. 如果当前行剩余宽度大于0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)，然后放入当前行。例如再放入一张4x9的图片，由于剩余宽度是2，这张图片会被压缩到2x5，再被放入第一行的末尾。此时该行高度为5：
    img

  3. 如果当前行剩余宽度为0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。此时所有行的总高度和就是这 N 张图片的排版高度。例如再放入11x1, 5x5, 3x4 的图片后，效果如下图所示，总高度为11：
    img

    现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 N 张图片中选择一张删除掉以降低总高度。他希望剩余N-1张图片按原顺序的排版高度最低，你能求出最低高度是多少么？

题解

预处理以第 i 张图为行首的最低高度，然后枚举删图。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define inlld(lld) scanf("%lld", &lld)
#define inlf(f) scanf("%lf", &f)
#define ind(d) scanf("%d", &d)
#define ins(s) scanf("%s", s)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef std::pair<long long, long long> pll;
typedef std::vector<long long> vll;
typedef std::pair<int, int> pii;
typedef unsigned long long ull;
typedef std::vector<int> vii;
typedef long double db;
typedef long long ll;
const db pi = acos((db)-1);
const ll inf =0x3f3f3f3f;
const ll mod = 1e9+7;
const int N = 1.1e5;
const db eps = 1e-8;
using namespace std;
int sign(db a) { return a < -eps ? -1 : a > eps; }
int db_cmp(db a, db b){ return sign(a-b); }

pii a[N],b[N];
int suf[N];
int main() {
#ifdef PerpEternal
    // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m,n,w,h;
    scanf("%d%d",&m,&n);
    for0(i,n){
        scanf("%d%d",&w,&h);
        a[i]=pii(w,h);
    }
    for0(i,n){
        w=m; 
        h=0;
        int len=i;
        for(;len<n&&w;len++){
            if(w>=a[len].first){
                w-=a[len].first;
                h=max(h,a[len].second);
            }else{
                int th=ceil(a[len].second*w*1.0/a[len].first);
                w=0;
                h=max(h,th);
            }
        }
        // cout<<h<<endl;
        b[i]=pii(len,h);
    }
    // puts("");
    // for0(i,n)cout<<b[i].first<<' '<<b[i].second<<endl;
    for(int i=n-1;i>=0;i--){
        suf[i]=suf[b[i].first]+b[i].second;
    }
    // for0(i,n)cout<<suf[i]<<endl;
    int ans=inf,flag=0,tot=0;
    while(flag<n){
        for(int i=flag;i<b[flag].first;i++){
            w=m; 
            h=0;
            int len=flag;
            for(;len<n&&w;len++){
                if(len==i)continue;
                if(w>=a[len].first){
                    w-=a[len].first;
                    h=max(h,a[len].second);
                }else{
                    int th=ceil(a[len].second*w*1.0/a[len].first);
                    w=0;
                    h=max(h,th);
                }
            }
            ans=min(ans,tot+h+suf[len]);
        }
        tot+=b[flag].second;
        flag=b[flag].first;
        // tot+=
    }
    printf("%d\n",ans);
    return 0;
}