[题解] luogu P1120 小木棍

长度相等题目大意: 给你n(n<=65)个长度不超过50的小木棍, 他们可以拼成一些长度相等的大木棍, 让你求出一种方案使得大木棍长度最短

Sol:DFS + 剪枝

代码中有解释。

#include <bits/stdc++.h>

int A[70], n, tap, Sum;
bool Bok[70];

bool DFS(int, int, int);

int main() {
    scanf("%d", &tap);
    while(scanf("%d", &tap) > 0) 
        if(tap <= 50) Sum += (A[++n] = tap);

    std::sort(A + 1, A + 1 + n); //排序, 使得从n到1开始拼时可以减少搜索状态。因为拼接所需的大木棍比小木棍要少。
    
    for(int i = n; i >= 2; i --) //枚举原始木棍的数量, 数量越多长度越短, 及更优。 
        if((Sum % i) == 0) { //判断是否有可能为正确数量, 因为长度是正整数。
            if(DFS(i, 0, n)) {
                tap = Sum / i; //用全局变量tap记录长度, 在DFS函数中有用
                printf("%d\n", Sum / i); break; // 第一次搜到的可行解一定是最优的, 直接跳出

            } else continue; //可写可不写。
        } 
    return 0;
}

bool DFS(int Cnt, int Now, int Lst) { //Cnt为需要拼接的数量, Now为目前的原始木棍已拼接的长度, Lst为上次所用的木棍的长度。
    if(Cnt == 0) return true; //如果拼接完成了所有木棍, 返回真
    
    if(Now == tap) return DFS(Cnt - 1, 0, n); //这根原始木棍拼完了的话, 拼下一根
    
    int Wrong = -1; //优化1: 当尝试使用第i根小木棍失败时, 其他和A[i]长度一致的小木棍都不能使用(这个很显然)
    for(int i = Lst; i >= 1; i --) //从第Lst根小木棍开始尝试, 优先拼长的。上文已讲
        if((!Bok[i]) && A[i] != Wrong) {
            if(A[i] > tap) return false; //一根小木棍的长度就超过了原始木棍长, 方案肯定不行。
            if(A[i] + Now <= tap) { //合法的话
                Bok[i] = true; // ← 基本操作
                if(DFS(Cnt, Now + A[i], i - 1)) return true; //尝试是否可行
   //基本操作 →  Bok[i] = false, Wrong = A[i];  //既然到了这里(上面if为假), 说明不可行, 所有与其长度一致的都不行
                if((!Now) || A[i] + Now == tap) return false; //优化重点: 如果当前已拼的长度为0但用这根木棍拼却不可行, 说明无论如何都无法成功。 因为每根小木棍是必须要用的; 如果用这根木棍拼好了一根原始木棍, 但仍然不可行, 也是无法成功的。 因为你就算用一些更小的木棍来顶替这根的位置, 但他们的位置同样需要这根木棍来顶替。 而这根木棍在这里不行, 在那些小木棍里的位置上必然不行, 根据贪心原理。   
            }
        }
    return false; //每根木棍都不行, 自然不行
}    
Last modification:March 2nd, 2019 at 08:34 pm

6 comments

  1. marTixx

    orzorz

    1. czy
      @marTixx

      tql

  2. JRLC

    大佬们谦虚了

    1. Garbage
      @JRLC

      明明是LC太谦虚了

  3. Illusions

    太强了

  4. fpjo

Leave a Comment