[题解] [洛谷 P1120] 小木棍

Floyd3265 / 2024-04-24 / 原文

[洛谷 P1120] 小木棍

题目描述

有若干个长度相同的木棍，在被任意地切割后变成了 $n$ 段小木棍，每段的长度为 $a_i$ 问最开始的木棍最短是多长？

输入格式

第一行是一个整数 $n$ ，表示小木棍的个数。

第二行有 $n$个整数，表示各个木棍的长度 $a_i$

输出格式

一行一个整数 $n$ ，表示答案。

题解

参考：https://www.luogu.com.cn/article/fxoshw2y

本题是经典搜索题。

基本的搜索思想是枚举木棍本来的长度（答案），之后通过dfs进行验证。验证的过程就是通过将木棍拼起来，凑出目标长度基本的搜索流程如下：

dfs (当前的木棍的长度、目前拼凑后的木棍数) {
    如果当前的木棍长度等于目标长度，说明这一根拼完了，有两种情况：
        1. 所有木棍都拼完了，得到了一个解，更新答案
        2. 还没拼完，开始拼下一个木棍：找一节没有被拼过的木棍开拼下一根：dfs (找到的木棍长度、木棍数 + 1)
    这一根没有拼完，继续拼：
        找到一根还没有用过的木棍，拼到现在这一根上面：dfs (当前的木棍长度 + 新拼的一段、木棍数)
}

这么简单的暴力怎么能通过这么恶心的题呢？故优化：

将木棍从大到小排序，能够提高搜索效率
在拼木棍的时候，如果长度 $a_i$ 的不行，就没必要再看和 $a_i$ 一样长的了，故记录一个 $next_i$ 以记录这个长度的最后一个木棍的位置
只搜索长度小于等于还需要的木棍长度的木棍，这一部分可以用二分进一步优化
由于枚举是从小到大，那么第一次枚举到了可行解就是最优解，直接退出搜索
如果当前剩余的未拼长度=当前木棍的长度或本来的长度，且一次搜索没有搜到可行解，直接返回修改前面的部分。
只考虑目标长度能被总长度整除的情况
只考虑目标长度不大于和的一半的情况

优化5的原因如下：

如果未拼长度等于当前木棍的长度，那么这根木棍显然是要拼到这的，因为把剩下的都拼到这和拼这个等效，不如用这个完整的，所以这是有解的必要条件。

如果未拼长度等于原长，则说明还没开始拼，只要它能用上就有解，无解说明这个棍子用不上，这种情况下不肯能有可行解，所以这也是有解的必要条件。

调试过程

一开始我把拼下一根木棍和在现在这根后面接木棍的循环写到一起了 ~~（因为懒）~~ 。但这样会导致拼下一根木棍的搜索多进行很多次，原因是重复搜索了用相同的木棍但用不同顺序拼起来的情况。

此外，对于优化3,我一开始只是在循环里加了个判断，但这样实际无法缩小循环次数，$a$ 已经排好序了，直接从下一个棍子开始找就行了，所以修改了循环条件为 $x + 1$ （ $x$ 是当前棍子的位置），通过了此题。

题外话，这题虽然卡时间很厉害，但卡常不严重，cin/cout也能顺利通过

AC代码

#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

const int MAXN = 103;

int n;
int a[MAXN];

int ans = 1e9, sum;
bool vis[MAXN];
int nxt[MAXN];
void dfs(int x, int len, int tar, int cnt) { // 当前棍子的位置，已经拼了的长度，目标长度，当前拼的大棍子的编号
    vis[x] = true; //这根棍子用过了
    int rest = tar - len; // 还要拼的长度
    if (!rest) { // 这根拼完了，拼下一根
        if (cnt == sum / tar) { // 拼好了所有棍子，输出答案然后润
            ans = min(ans, len);
            cout << ans << '\n';
            exit(0);
        }
        // 找第一根还没用的棍子
        int i;
        for (i = 1; i <= n; i++) {
            if (!vis[i]) break;
        }
        // 开始用找到的第一根棍子拼下一根大棍
        dfs(i, a[i], tar, cnt + 1);
    }
    for (int i = x + 1; i <= n; i++) {
        if (vis[i]) continue;
        // 合并到当前木棍上
        if (len + a[i] <= tar && a[i] <= rest) { // 剪枝
            dfs(i, len + a[i], tar, cnt);
            if (rest == a[i] || rest == tar) { // 优化5
                vis[x] = false;
                return;
            }
            i = nxt[i]; // 优化2
        }
    }
    vis[x] = false;
}

inline bool cmp(int x, int y) {
    return x > y;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a + 1, a + 1 + n, cmp);
    nxt[n] = n;
    for (int i = n - 1; i > 0; i--) {
        if (a[i] == a[i + 1]) nxt[i] = nxt[i + 1];
        else nxt[i] = i;
    }
    for (int i = a[1]; i <= sum / 2; i++) {
        if (sum % i != 0) continue;
        dfs(1, a[1], i, 1);
    }
    cout << sum << '\n';
    return 0;
}