IOI2009 raisins 题解

Edited on | In | Comments:

Problem

问题描述：

普罗夫迪夫的著名巧克力大师Bonny需要切开一板带有葡萄干的巧克力。巧克力是一个包含许多相同的方形小块的矩形。小块沿着巧克力的边排列成$n$行$m$列，即共有$n×m$块。每个小块上有$1$个或多个葡萄干，没有葡萄干在小块的边上或者跨过两个小块。

最开始，巧克力是一整块。Bonny需要把它切成上述的$n×m$个独立的小块。因为Bonny很忙，她需要她的助手Sly Peter帮她切。Peter只能从一端到另一端切直线并且他要为他的每一刀得到报酬。Bonny手头没有钱，但是她有足够的葡萄干，所以她提出用葡萄干付给Peter。Sly Peter同意接受葡萄干，但是有下面的条件：每次他把给定的一块巧克力切成两小块，他都要得到和那块给定的巧克力上葡萄干数目相同的葡萄干。

Bonny想要付给Peter尽可能少的葡萄干。她知道这$n×m$个小块中每一个小块上葡萄干的数目。她可以选择递给Peter的巧克力的顺序，也可以告诉Peter如何切(横切还是竖切)以及从哪里切。请告诉Bonny如何把巧克力切成一个个独立的小块。使她能够付给Sly Peter尽可能少的葡萄干。

任务

写一个程序，给定每个小块上葡萄干的数目，计算Bonny要付给Sly Peter的最少的葡萄干的数目。

数据规模

$1≤n,m≤50$ 巧克力两条边上小块的数目

$1≤R_{k,p}≤1,000$ 第$k$行第$p$列的小块上的葡萄干数目

有25分的评测数据，$n,m≤7$。

输入

你的程序必须从标准输入中读取下列数据：

第一行包含整数$n$和$m$，以一个空格隔开。

接下来的n行描述了每个小块上葡萄干的数目。这n行中第$k$行描述的是第$k$行小块巧克力。每行包含$m$个整数，分别以一个空格隔开。这些整数描述的是该行从左到右的小块。第$k$行的第$p$个整数表示位于第$k$行第$p$列的小块上的葡萄干数目。

输出

你的程序必须向标准输出写入一行，该行包含一个整数Bonny：要付给Sly Peter的最少的葡萄干的数目。

样例

1
2
3
4
Input #1
2 3
2 7 5
1 9 5
1
2
Output #1
77

img

img

一种可能的花费$77$的切法(许多种之一)：

第一刀，将第$3$列切下，Bonny要付给Peter$29$个葡萄干。

接下来，Bonny将小的一块给Peter：两小块各有$5$个葡萄干的那块，Peter把它从中切开得到$10$个葡萄干。

接下来，Bonny给Peter第一刀后较大的一块：有$2,7,1$和$9$个葡萄干的那块，Bonny要求Peter横切，即将第一和第二行分开，得到$19$个葡萄干。

接下来，Bonny要求Peter切开左上部的一块，付$9$个葡萄干。最后，Bonny要求Peter切开左下部的一块，付$10$个葡萄干。

Bonny的总花费是$29+10+19+9+10=77$个葡萄干。没有其他的切法能够花费更少的葡萄干而把该巧克力切成$6$小块。

Solution

二分错解

我最先的睿智想法：既然越少越好，那么

——–以下是扯淡内容，读者请不要相信——–

左右两边越平均越好（不知道哪里来的稀奇想法）

——–以下不是扯淡内容——–

对于这种题，显然做一个前缀和。

又因为$1≤n,m≤50$，则可以做$4$维前缀和，把每一个可能割出来的巧克力块上的葡萄干数全部记录下来（有的是空间）。

接下来进行分治，根据我的稀奇想法，二分前缀和找到平衡线使割开的两部分上的葡萄干数尽量接近。

接下来就是递归啊递归啊递归啊递归…

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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50 + 5;
int n, m;
long long raisin[MAXN][MAXN];
long long sum[MAXN][MAXN], cnt[MAXN][MAXN][MAXN][MAXN];
long long ans;

long long area(int ldx, int ldy, int urx, int ury)
{
    return sum[urx][ury] - sum[ldx - 1][ury]
        - sum[urx][ldy - 1] + sum[ldx - 1][ldy - 1];
}

long long dfs(int ldx, int ldy, int urx, int ury, bool k) //k表示横向切还是纵向切
{
    int l, r;
    long long ans1 = LONG_LONG_MAX, ans2 = LONG_LONG_MAX;
    double half = cnt[ldx][ldy][urx][ury] / 2.0; //当前处理的巧克力上葡萄干总数的一半，不用double也行
    if (k)
    {
        //二分思想：左右两边最接近，即左边和总数一半接近，二分刀切在哪里
        l = ldx, r = urx;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (cnt[ldx][ldy][mid][ury] > half) r = mid;
            else l = mid;
        }
        //选l和r中离总数一半最接近的切
        int flag = (fabs(half - cnt[ldx][ldy][l][ury]) < fabs(cnt[ldx][ldy][r][ury] - half) ? l : r);
        if (flag == ldx && ldy == ury) ans1 = cnt[ldx][ldy][ldx][ldy]; //切下来边长为1
        else
        {
            if (flag != ldx) ans1 = dfs(ldx, ldy, flag, ury, 1);  //长>1，可以切
            if (ldy != ury)    ans1 = min(ans1, dfs(ldx, ldy, flag, ury, 0)); //宽>1，可以切
        }
        if (flag + 1 == urx && ldy == ury) ans2 = cnt[urx][ury][urx][ury];
        else
        {
            if (flag + 1 != urx) ans2 = dfs(flag + 1, ldy, urx, ury, 1);
            if (ldy != ury) ans2 = min(ans2, dfs(flag + 1, ldy, urx, ury, 0));
        }
        return ans1 + ans2 + cnt[ldx][ldy][urx][ury];
    }
    else
    {
        l = ldy, r = ury;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (cnt[ldx][ldy][urx][mid] > half) r = mid;
            else l = mid;
        }
        int flag = (fabs(half - cnt[ldx][ldy][urx][l]) < fabs(cnt[ldx][ldy][urx][r] - half) ? l : r);
        if (flag == ldy && ldx == urx) ans1 = cnt[ldx][ldy][ldx][ldy];
        else
        {
            if (flag != ldy) ans1 = dfs(ldx, ldy, urx, flag, 0);
            if (ldx != urx) ans1 = min(ans1, dfs(ldx, ldy, urx, flag, 1));
        }
        if (flag + 1 == ury && ldx == urx) ans2 = cnt[urx][ury][urx][ury];
        else
        {
            if (flag + 1 != ury) ans2 = dfs(ldx, flag + 1, urx, ury, 0);
            if (ldx != urx) ans2 = min(ans2, dfs(ldx, flag + 1, urx, ury, 1));
        }
        return ans1 + ans2 + cnt[ldx][ldy][urx][ury];
    }
}

int main()
{
    freopen("raisins.in", "r", stdin); freopen("raisins.sol", "w", stdout);
    cin >> n >> m;
    if (n == 1 && m == 1) { cin >> raisin[1][1]; cout << 0 << endl; return 0; }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> raisin[i][j];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1]
            - sum[i - 1][j - 1] + raisin[n - j + 1][i];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= i; k++)
                for (int l = 1; l <= j; l++)
                    cnt[k][l][i][j] = area(k, l, i, j);
    if (n != 1) ans = dfs(1, 1, m, n, 0);
    if (m != 1) ans = min(ans, dfs(1, 1, m, n, 1));
    cout << ans - cnt[1][1][m][n] << endl;
    return 0;
}

完美地WA了。

找了两天bug没找出来，只好否认：自己的算法错了。

于是一时性起：

不用二分了，我倒要看看暴力能拿几分！

正解

正解就是暴力。

把上面一段代码的二分部分改成

1
for (int flag = ldx; flag < urx; flag++)

就能TLE。（手动滑稽

空间多到溢出的我又开始挥霍：记忆化每一个巧克力块的最小切割支出。

然而还是TLE了。

又想了半天优化，突然发现，之前是因为不能把边长为1的线段进行二分才加了那么多判断的，现在可是暴力啊，循环条件直接给舍了边长为1的情况了，于是愉快地把特判给省了。

然后就能发现，$k=true$或$k=false$是一样的情况，舍了。

就这么AC了。

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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50 + 5;
int n, m;
int raisin[MAXN][MAXN];
int sum[MAXN][MAXN], cnt[MAXN][MAXN][MAXN][MAXN];
int memory[MAXN][MAXN][MAXN][MAXN];  //记忆化
int ans = INT_MAX;

int dfs(int ldx, int ldy, int urx, int ury)
{
    if (memory[ldx][ldy][urx][ury]) return memory[ldx][ldy][urx][ury]; //记忆化
    if (ldx == urx && ldy == ury) return cnt[ldx][ldy][urx][ury]; //边长为1
    int pay, tot = INT_MAX;
    for (int flag = ldx; flag < urx; flag++) //横向切
    {
        pay = dfs(ldx, ldy, flag, ury) + dfs(flag + 1, ldy, urx, ury);
        if (tot > pay) tot = pay;
    }
    for (int flag = ldy; flag < ury; flag++) //纵向切
    {
        pay = dfs(ldx, ldy, urx, flag) + dfs(ldx, flag + 1, urx, ury);
        if (tot > pay) tot = pay; //pay取最小值
    }
    memory[ldx][ldy][urx][ury] = tot + cnt[ldx][ldy][urx][ury];
    //返回：自己的花费+上一层自己一块所占的花费
    return memory[ldx][ldy][urx][ury];
}

int main()
{
    cin >> n >> m;
    //边长为1不用切，输出0
    if (n == 1 && m == 1) { cin >> raisin[1][1]; cout << 0 << endl; return 0; }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> raisin[i][j];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1]
            - sum[i - 1][j - 1] + raisin[n - j + 1][i];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= i; k++)
                for (int l = 1; l <= j; l++)
                    cnt[k][l][i][j] = sum[i][j] - sum[k - 1][j]
                        - sum[i][l - 1] + sum[k - 1][l - 1];
    //以上前缀和
    ans = dfs(1, 1, m, n);
    cout << ans - cnt[1][1][m][n] << endl; //由于第一刀没有再上一层，减去总数
    return 0;
}

Data

测试数据 提取码：0q3s