首页 > 其他 > 详细

POJ1011 Sticks

时间:2019-02-12 01:01:47      阅读:209      评论:0      收藏:0      [点我收藏+]

小木棍

dfs 剪枝

  • 把所有木棍从大到小排序 优化搜索顺序(较大的木棍更不容易凑出需要的长度,使之后的剪枝更早发生)

  • 枚举可能的原始木棍长度,(注意这里不满足单调性,不能二分答案),这里可以把最长的一根现有木棍作为枚举的下界,上界为所有木棍更总长度。

  • 答案只可能为总长度的因数,在枚举过程中其他的数可直接排除。

  • dfs过程中,若剩下还要拼的长度比第n根碎木棍(最短的那根)还短,那么一定拼不成。

  • 若有几根相同长的木棍,其中拿出一根拼失败了,剩下的也一定会失败,不用再dfs了(这处剪枝很重要,因为每根木棍长度在50以内,会有很多重复长度)。

  • 对于当前枚举的原始木棍长度,如果第一次用到的碎木棍拼失败了,那么这个原始木棍长度不合适,直接return。因为那根碎木棍无论放在哪都不合适。

  • 对于当前枚举的原始木棍长度,如果有一次选用的碎木棍恰能把那根拼起来,但dfs递归之后却失败了,那么直接return。因为贪心的想,木棍按长度从大到小排,这次用上恰能补上空隙的长木棍之后都失败了,那么如果用较短的木棍去补这个空隙,之后不可能更优。

    ?

    丑陋的代码

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>
    using namespace std;
    const int maxn=100;
    int low,sum,n,len,cnt,tot;
    int a[maxn];
    bool used[maxn],judge;
    inline bool cmp(const int &a,const int &b){
        return a>b;
    }
    void dfs(int now,int sum,int last){
    //now--正在拼第几根原始木棍 sum--当前正在拼的这根已经拼好的长度 
    //last--上次选择的木棍编号(便于剪枝) 
        if(now>cnt){
            judge=true;
            return;
        }
        if(sum==len) dfs(now+1,0,1);
        if(len-sum<a[n]) return;//剪枝,若剩下还要拼的长度比第n根碎木棍(最短的那根)还短,那么一定拼不成
        int fail=0;//上次拼失败的木棍长度 
        for(int i=last;i<=n;++i){
            if(used[i]||sum+a[i]>len||a[i]==fail) continue;
            used[i]=true;
            dfs(now,sum+a[i],i+1);
            if(judge) return;//若已经成功就没必要再拼了 
            used[i]=false;//回溯 
            fail=a[i];
            if(sum==0||sum+a[i]==len) return;
        }
    }
    int main(){
        while(scanf("%d",&n) && n){
            low=sum=tot=0;
          for(int i=1,x;i<=n;++i){
              scanf("%d",&x);
              if(x<=50){  
                  a[++tot]=x;
                  low=max(low,x);//预估下界
                  sum+=x;
              }
          }
          n=tot;
            sort(a+1,a+1+n,cmp);//优化搜索顺序
            for(len=low;len<=sum;++len){
                if(sum%len) continue;//答案只可能为总长度的因数 
                memset(used,0,sizeof(used));//每次都要重置 
                judge=0;
                cnt=sum/len;
                dfs(1,0,1);
                if(judge) break;
            }
            printf("%d\n",len);
        }
        return 0;
    }

    dfs最好写返回值为bool类型的,如蓝书(李煜东《算法竞赛进阶指南》)代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int a[100], v[100], n, len, cnt;
    
    // 正在拼第stick根原始木棒(已经拼好了stick-1根)
    // 第stick根木棒的当前长度为cab
    // 拼接到第stick根木棒中的上一根小木棍为last
    bool dfs(int stick, int cab, int last) {
      // 所有原始木棒已经全部拼好,搜索成功
      if (stick > cnt) return true;
      // 第stick根木棒已经拼好,去拼下一根
      if (cab == len) return dfs(stick + 1, 0, 1);
      int fail = 0; // 剪枝(2)
      // 剪枝(1):小木棍长度递减(从last开始枚举)
      for (int i = last; i <= n; i++)
          if (!v[i] && cab + a[i] <= len && fail != a[i]) {
              v[i] = 1;
              if (dfs(stick, cab + a[i], i + 1)) return true;
              fail = a[i];
              v[i] = 0; // 还原现场
              if (cab == 0 || cab + a[i] == len) return false; // 剪枝(3,4)
          }
      return false; // 所有分支均尝试过,搜索失败
    }
    
    int main() {
      while (cin >> n && n) {
          int sum = 0, val = 0, m = 0;
          for (int i = 1; i <= n; i++) {
              int x;
              scanf("%d", &x);
              if (x <= 50) {
                  a[++m] = x;
                  sum += a[m];
                  val = max(val, a[m]);
              }
          }
          n = m;
          sort(a + 1, a + n + 1);
          reverse(a + 1, a + n + 1); 
          for (len = val; len <= sum; len++) {
              if (sum % len) continue;
              cnt = sum / len; // 原始木棒长度为len,共cnt根
              memset(v, 0, sizeof(v));
              if (dfs(1, 0, 1)) break;
          }
          cout << len << endl;
      }
    }

    ?

POJ1011 Sticks

原文:https://www.cnblogs.com/yu-xing/p/10363724.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!