一般的，在碰到搜索题的时候，我的反应是：woc，这也能搜索？事实证明，我还是too young.

这是一道重在剪枝的神奇DFS题。

题面

  • 据说,少林寺的镇寺之宝,是救秦王李世民的十三棍僧留下的若干根一样长的棍子。
  • 在民国某年,少林寺被军阀炮轰,这些棍子被炸成N N 节长度各异的小木棒。
  • 战火过后,少林方丈想要用这些木棒拼回原来的棍子。可他记不得原来到底有几根棍子了,只知道古人比较矮,且为了携带方便,棍子一定比较短。他想知道这些棍子最短可能有多短。

看到这个题面之后，我整个人都不好了qwq

题目大意

  • 给定NN节长度各异的小木棒，不剩余地拼成若干节长度相等的少林神棍，求神棍最短可以有多短。

解题思路

枚举

  • 可能拼成的棍子长度
  • 长度从最长的那根木棒开始枚举到木棒总长的一半
  • 若枚举到的长度不能整除木棒总长度，则不去搜索

搜索

搜索的过程，就是我们尝试着拼神棍的过程

  • 如何拼完这一组神棍呢？
    • 一根一根的拼棍子
    • 如果拼完第ii根棍子之后，发现第i+1i+1根棍子拼不成了，那就推翻第ii根棍子的拼法
    • 有可能一直向前推翻第一根的拼法

搜索状态

发现能搜索以后，就要确定搜索状态了

  • 我们设状态为一个二元组(R,M)(R,M)。
    • RR表示还没有用的木棒数
    • MM表示当前拼的这根棍子剩余未填满的长度
  • 本题的初始状态和结束状态是什么？
  • 假设共有NN根木棒，当前枚举到的长度为LL。
    • 初始状态：(N,L)(N,L)
    • 结束状态：(0,0)(0,0)

开始搜索

我也不废话了，伪代码参上

Dfs的基本递推关系:bool Dfs(int R, int M) {
    if( R == 0 && M == 0)	return true; //拼接任务完成 
    如果能找到一根长为S(S <= M)的木棒,拼在当前棍子上,然后	Dfs(R – 1,M - S);	如果找不到:return false; 
}

这里要注意的是我们首先要对长度排序，从大到小枚举

剪枝

如果按照之前的搜法，那么一定会TLE

所以，我们需要出动暴力大杀器——剪枝

剪枝1

  • 如果在当前状态下确定了一根不能使用的木棒，那么当我们弃用它以后，当前状态下和它长度同的木棒都不再使用。
  • 正确性显然

剪枝2

  • 由于拼接失败，我们需要拆掉某根棍子时，如果我们一直拆解到它的第一根木棒，那么我们就不再动它，去看它的上一根棍子，如果它没有上一根棍子，则此长度不合法
  • 如果拆掉第一根木棒，我们假设它在之后能被使用，而现在已知序列是有序的，那么如果之后某种拼法能使得当前第一根棍子被用到，那么它在之前序列一定不会被拆掉。

剪枝3

  • 当我们需要拆解某根已经拼好的棍子时，不要拆掉最后的那根木棒反而用更小的木棒来代替。
  • 如果这样就能拼上，那么我们用用来代替最后长木棒的几根短木棒来代替那根长木棒也能拼上。

剪枝4

  • 如果当前需要加的木棒不是当前棍子的第一根，那么我们不能从最长的木棒往下枚举，而是从最近使用过的那根之后的一根开始向下枚举。
  • 这样可以避免先使用长的后使用短的的情况。

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int n, l; bool used[65];
vector <int> len;
int last;
bool dfs (int r, int m) {
    if (r == 0 && m == 0) return true;//搜索停止，达到条件返回true，表示枚举的长度可行
    if (m == 0) m = l;//如果已经拼完一根，那么就再接着往下拼
    int S = 0;
    if (m != l) S = last + 1;//剪枝4，保证递减拼
    for (int i = S; i < n; i++) {
        if (!used[i] && len[i] <= m) {
            if (i > 0) {
                if (!used[i - 1] && len[i] == len[i - 1]) continue;//剪枝1，保证相同长度的木棒不在同一位置多次用
            }
            used[i] = true; last = i;//标记此根为使用过，记录本次加入的木棒
            if (dfs(r - 1, m - len[i])) return true;
            else {
                used[i] = 0;//回溯，有可能之后还能用到这根木棒
                if (len[i] == m || m == l) return false;//剪枝2，3
            }
        }
    }
    return false;
}
int main () {
    while (1) {
        cin >> n;
        if (n == 0) break;//Blocks of datas, 读入0终止
        len.clear();//每次清一遍储存长度的数组
        int totallen = 0;
        for (int i = 0; i < n; i++) {
            int x; cin >> x;
            len.push_back(x);
            totallen += x;
        }
        sort (len.begin(), len.end(), greater<int>());//从小到大排序
        for (l = len[0]; l <= totallen / 2; l++) {
            if (totallen % l) continue;
            memset(used, 0, sizeof(used));
            if (dfs(n, l)) {cout << l << endl; break;}//因为是从小到大枚举，所以验证一个答案正确就可以输出了
        }
        if (l > totallen / 2) cout << totallen << endl;
    }
    return 0;
}

团长在POJ和HDU上都成功拯救了少林神棍，但是原题并不叫拯救少林神棍，而是叫Sticks，很无聊的题面，某不远透露姓名的薛定谔同学竟然告诉我这是一道POJ上的中文题，害的我一阵好找。。。。