题解 P1651 【塔】

K2sen · 2020-07-12 08:29:47 · 题解

讲前瞎扯

~~我dfs过了~~

发现题解里边好像都是dp的

因为我太菜了，看不懂dp方程，然后就自己dfs水过了,,

正题

首先我们的dfs应该是这个样子的

用now来表示用到了那个方块, h1 h2 分别是两座塔的高度

然后我们就可以根据题意进行dfs

void dfs(int now, int h1, int h2) {
    if (now == n + 1) {//如果dfs完了，那就退出
        if (h1 == h2) ans = max(ans, h1);
        return;
    }
    dfs(now + 1, h1 + a[now], h2);//可以选择把当前的方块
    dfs(now + 1, h1, h2 + a[now]);//放到第1或者2堆
    dfs(now + 1, h1, h2);//当然也可以不放
}

考虑如何剪枝

#### 可行性剪枝我们可以感性的理解一下，如果$h_1$加上剩下的方块还比$h_2$矮, 那么就没有必要进行了,$h_2$同理 ```cpp if (h1 + sum[n] - sum[now - 1] < h2) return; if (h2 + sum[n] - sum[now - 1] < h1) return; ``` #### 最优性剪枝我们用一个$ans$来记录的最优解，发现如果$h_1$加上剩下所有的方块，都比$ans$小，那么就没有必要进行了，$h_2$同理. 而且，如果两座塔的高度加起来再加上所有剩下的方块比$ans$的两倍还要小的话,也没有必要进行了，所以直接返回就可以了, ```cpp if (h1 + h2 + sum[n] - sum[now - 1] <= ans * 2) return; if (h1 + sum[n] - sum[now - 1] <= ans) return; if (h2 + sum[n] - sum[now - 1] <= ans) return; ``` #### code ```cpp #include <bits/stdc++.h> #define ll long long #define N 100010 #define M 60 using namespace std; int n, a[M], ans; int sum[M]; int read() { int s = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); return f ? -s : s; } bool cmp(int a, int b) { return a > b; } void dfs(int now, int h1, int h2) { if (now == n + 1) { if (h1 == h2) ans = max(ans, h1); return; } if (h1 + h2 + sum[n] - sum[now - 1] <= ans * 2) return; if (h1 + sum[n] - sum[now - 1] <= ans) return; if (h2 + sum[n] - sum[now - 1] <= ans) return; if (h1 + sum[n] - sum[now - 1] < h2) return; if (h2 + sum[n] - sum[now - 1] < h1) return; dfs(now + 1, h1 + a[now], h2); dfs(now + 1, h1, h2 + a[now]); dfs(now + 1, h1, h2); } int main() { n = read(); for (int i = 1; i <= n; i++) a[i] = read(); sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i]; dfs(1, 0, 0); if (ans == 0) puts("-1"); else cout << ans; } ``` 然后我们发现过不了，获得了80分的好成绩，两个点T得死死的... 是时候祭出终极大杀器——记忆化搜索了 #### 记忆化搜索我们需要把dfs中的返回值改成int,因为需要记忆化我们要用一个东西存一下每次的状态，但是我们发现$h_1,h_2 \leq 5e5

所以开数组是不可能了，所以我们选择map+pair

map<pair<int, pair<int, int> >, int>ma;

我们在每一次dfs完成之后记录一下当前这次dfs所分出去的三次dfs的最优解

just \ like \ this

int s = 0;
s = max(s, dfs(now + 1, h1 + a[now], h2));
s = max(s, dfs(now + 1, h1, h2 + a[now]));
s = max(s, dfs(now + 1, h1, h2));
ma[make_pair(now, make_pair(h1, h1))] = s;

在下一次找到和当前状态相同的时候可以直接返回

just \ like \ this

if (ma[make_pair(now, make_pair(h1, h1))])
    return ma[make_pair(now, make_pair(h1, h1))];

而且上边我们剪的枝可以直接返回-1，因为那些无所谓.

code

#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define M 60

using namespace std;
int n, a[M], ans;
int sum[M];
map<pair<int, pair<int, int> >, int>ma;

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

bool cmp(int a, int b) {
    return a > b;
}

int dfs(int now, int h1, int h2) {
    if (now == n + 1) {
        if (h1 == h2) {
            ans = max(ans, h1);
            return h1;
        } 
        return -1;
    }
    if (ma[make_pair(now, make_pair(h1, h1))])
        return ma[make_pair(now, make_pair(h1, h1))];
    if (h1 + h2 + sum[n] - sum[now - 1] <= ans * 2) return -1;
    if (h1 + sum[n] - sum[now - 1] <= ans) return -1;
    if (h2 + sum[n] - sum[now - 1] <= ans) return -1;
    if (h1 + sum[n] - sum[now - 1] < h2) return -1;
    if (h2 + sum[n] - sum[now - 1] < h1) return -1;
    int s = 0;
    s = max(s, dfs(now + 1, h1 + a[now], h2));
    s = max(s, dfs(now + 1, h1, h2 + a[now]));
    s = max(s, dfs(now + 1, h1, h2));
    ma[make_pair(now, make_pair(h1, h1))] = s;
    return s;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
    dfs(1, 0, 0);
    if (ans == 0) puts("-1");
    else cout << ans;
}

最后放一张惊险又刺激的AC图