塔

GitHub跳转原题关系图返回列表

设 dp[diff] 为当前两塔高度差为 diff 时较矮塔的最大高度，每个木块枚举放高塔、放低塔或不用即可完成差值 DP。

OJ: luogu

题目 ID: P1651

难度:普及+/提高

标签:动态规划背包dp

日期: 2026-06-19 13:53

目录

  1. 题意
  2. 思路
    1. 状态表
    2. DP 公式
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给出 N 个木块，每个木块有一个高度。

每个木块可以：

  • 放到第一座塔
  • 放到第二座塔
  • 或者不用

要求最终两座塔高度相同，并让这个相同高度尽量大。

思路

先看最直接的暴力：

cpp
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，每个木块三种选择，先生成完整选择序列再检查。

int n;
int h[25];
int choose_block[25]; // 0 不用，1 放左塔，2 放右塔
int ans;

void calc_height(int &left_sum, int &right_sum) {
    left_sum = 0;
    right_sum = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_block[i] == 1) {
            left_sum += h[i];
        } else if (choose_block[i] == 2) {
            right_sum += h[i];
        }
    }
}

bool check() {
    int left_sum, right_sum;
    calc_height(left_sum, right_sum);
    return left_sum == right_sum && left_sum > 0;
}

int calc_answer() {
    int left_sum, right_sum;
    calc_height(left_sum, right_sum);
    return left_sum;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_answer();
            if (ans < value) ans = value;
        }
        return;
    }

    // 第 dep 个木块的选择：0 不用，1 放左塔，2 放右塔。
    for (int i = 0; i <= 2; i++) {
        choose_block[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    ans = 0;
    dfs_choose(1);

    cout << ans << '\n';
    return 0;
}

brute.cpp 把每个木块看成三分支选择：choose_block[i] = 0/1/2 分别表示不用、放左塔、放右塔。递归先生成完整选择，叶子节点再检查两座塔是否等高，并统计高度。

这个做法很好理解，但复杂度是 3^N，只能做小数据验证。

关键在于状态应该怎么压。

如果只记录两座塔的高度差 diff，信息还不够；因为同样的差值，较矮塔越高显然越优。

所以设：

  • dp[diff] 表示当前两座塔高度差为 diff 时，较矮那座塔的最大高度

加入一个新木块高度 h 时，有三种转移：

  1. 不用它
    差值不变

  2. 放到较高塔
    新差值变成 diff + h，较矮塔高度不变

  3. 放到较矮塔
    这时可能会让两塔角色交换，但可以统一成：

    • new_diff = abs(diff - h)
    • new_low = dp[diff] + min(diff, h)

状态表

这张表说明 dp[diff] 的含义：

状态 含义
dp[diff] 当前两塔高度差为 diff 时，较矮塔的最大高度

最终当 diff = 0 时，两座塔等高，所以 dp[0] 就是答案。

DP 公式

设 dpddp_d 表示当前两座塔高度差为 dd 时，较矮塔的最大高度。加入一块高度为 hh 的木块时，有三种选择。

不放：

newd=max⁡(newd, dpd) new_{d}=\max(new_d,\ dp_d)

放到较高塔：

newd+h=max⁡(newd+h, dpd) new_{d+h}=\max(new_{d+h},\ dp_d)

放到较矮塔：

new∣d−h∣=max⁡(new∣d−h∣, dpd+min⁡(d,h)) new_{|d-h|}=\max(new_{|d-h|},\ dp_d+\min(d,h))

最终答案为：

dp0 dp_0

公式解释：状态只记录两塔高度差和较矮塔高度，因为较高塔高度可由两者推出。新木块可以不放、放高塔或放矮塔；放矮塔时较矮塔增加的高度是 min(diff,h)。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXS = 500005;
const int NEG_INF = -1000000000;

int n;
int h[55];
int dp[MAXS], ndp[MAXS];
int sum_h;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        sum_h += h[i];
    }

    for (int i = 0; i <= sum_h; i++) {
        dp[i] = NEG_INF;
    }
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int d = 0; d <= sum_h; d++) {
            ndp[d] = dp[d];
        }

        for (int d = 0; d <= sum_h; d++) {
            if (dp[d] == NEG_INF) {
                continue;
            }

            // 把当前木块放到较高的塔上，差值增大。
            ndp[d + h[i]] = max(ndp[d + h[i]], dp[d]);

            // 把当前木块放到较低的塔上。
            int new_diff = abs(d - h[i]);
            int new_low = dp[d] + min(d, h[i]);
            ndp[new_diff] = max(ndp[new_diff], new_low);
        }

        for (int d = 0; d <= sum_h; d++) {
            dp[d] = ndp[d];
        }
    }

    cout << dp[0] << '\n';
    return 0;
}

复杂度

  • 时间复杂度：O(N∗sumH)O(N * sumH)
  • 空间复杂度：O(sumH)O(sumH)

总结

这题的关键不是同时记两座塔各自多高，而是只记：

  • 高度差
  • 以及该差值下较矮塔的最优高度

这样状态就足够表达最优性，整个问题自然转成了差值 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析