• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Better man

            改變性格 改變命運!

             

            DFSID

             1 /*
             2 ID: hongfei5
             3 PROG: fence8 
             4 LANG: C++
             5 */
             6 /*
             7       dfsid(迭代加深搜索)
             8       適用于搜索樹又寬又深,但是可行解卻不是很深的題目
             9       廣度優(yōu)先搜索可能會空間不夠
            10 */
            11 //按大小排序后,則切割的木料中必然包含rail[0]
            12 #include <iostream>
            13 #include <algorithm>
            14 using namespace std;
            15 int n,m;//木板和木料的數(shù)目
            16 int rail[1025];
            17 int board[51];
            18 int remain[51];
            19 int best;
            20 long sum;
            21 long long waste,maywaste,tot[1025];//表示已經(jīng)不能再切的剩下的木料總和
            22 void dfs(int dep,int digit)
            23 {
            24       if(dep==0)
            25       {
            26             for(int i=digit;i<n;++i)
            27                   if(remain[i]>=rail[0])
            28                   {
            29                         printf("%d\n",best);
            30                         exit(0);
            31                   }
            32             return ;
            33       }
            34       for(int i=digit;i<n;++i)
            35             if(remain[i]>=rail[dep])
            36             {
            37                   long long oldwaste=waste;
            38                   remain[i]-=rail[dep];
            39                   if(remain[i]<rail[0]&&waste+remain[i]>maywaste)
            40                   {
            41                         remain[i]+=rail[dep];
            42                         continue;
            43                   }
            44                   if(remain[i]<rail[0])waste+=remain[i];
            45                   if(rail[dep-1]==rail[dep])dfs(dep-1,i);//如果rail[i]==rail[i-1],而第i塊木料在第K塊木板上切的,那么第i-1塊木料必定在大于等于K的木板上切出
            46                   else dfs(dep-1,0);
            47                   remain[i]+=rail[dep];
            48                   waste=oldwaste;
            49             }
            50 }
            51 int main()
            52 {
            53       freopen("fence8.in","r",stdin);
            54       freopen("fence8.out","w",stdout);
            55       scanf("%d",&n);
            56       for(int i=0;i<n;++i)
            57       {
            58             scanf("%d",&board[i]);
            59             remain[i]=board[i];
            60             sum+=board[i];
            61       }
            62       scanf("%d",&m);
            63       for(int i=0;i<m;++i)
            64             scanf("%d",&rail[i]);
            65       sort(board,board+n);
            66       sort(rail,rail+m);
            67       tot[0]=rail[0];
            68       int k=0;
            69       while(k<&& tot[k]<=sum){            //剪枝方法1 
            70             ++k;
            71             tot[k]=tot[k-1]+rail[k];
            72       }
            73       m=k;
            74       for(int i=m-1;i>=0;--i)
            75       {
            76             waste=0;
            77             maywaste=sum-tot[i];
            78             best=i+1;
            79             dfs(i,0);
            80       }
            81       printf("0\n");
            82       return 0;
            83 }
            迭代加深搜索 并不一定都要加深搜索深度 此題就是逐漸減少深
            1.很容易就能注意到,由于每塊rail的價值是相等的——也就是說切小的要比切大的來的劃算。那么我們在搜索能否切出i個rail的方案是自然要選最小的i個rail來切
            2.經(jīng)過一些實驗可以發(fā)現(xiàn),先切大的rail比先切小的rail更容易提前出解。同樣,[先切小的board比先切大的board更容易提前出解?]{注:好像先切大的board要比先切小的更快
            3.由于r最大可能是1023,但是rail長度的范圍卻只有0~128,這點提醒了我們有很多rail的長度會是相同的。所以我們要避免 冗余,優(yōu)化搜索順序。若有rail[i+1]=rail[i],則rail[i+1]對應的board一定大于等于rail[i]對應的board。可以 通過這種方法剪掉很多冗余的枝條
            4.相應的,如果board[i]=board[i+1],那么從board[i]切下的最大的rail一定大于等于從board[i+1]切下的最大的rail
            5.對于切剩下的board(無法再切下rail),統(tǒng)計一下總和。如果大于 board長度總和-rail長度總和,一定無解,可以剪枝。


            posted on 2009-01-30 18:12 SHFACM 閱讀(780) 評論(0)  編輯 收藏 引用

            導航

            統(tǒng)計

            常用鏈接

            留言簿(2)

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            99久久精品免费看国产| 午夜精品久久久内射近拍高清| 久久中文字幕人妻丝袜| 久久综合国产乱子伦精品免费| 麻豆成人久久精品二区三区免费| 国产精品免费看久久久| 国产一区二区精品久久岳| 欧美性猛交xxxx免费看久久久| 久久人人爽人人爽人人av东京热 | 亚洲精品国产美女久久久| 久久ww精品w免费人成| 久久国产免费直播| 久久AV高清无码| 狠狠色丁香婷婷久久综合五月| 久久久久国产一级毛片高清版| 四虎影视久久久免费| 久久久久国产一级毛片高清版| 久久亚洲视频| 国产精品VIDEOSSEX久久发布| 日韩精品久久久久久久电影蜜臀| 国产精品美女久久久网AV| 久久精品国产第一区二区三区 | 伊人久久综合成人网| 久久久久久久亚洲精品| 国产成人精品久久二区二区| 国色天香久久久久久久小说| 久久亚洲中文字幕精品一区四| 久久99精品国产自在现线小黄鸭| 久久综合给合综合久久| 青青青国产成人久久111网站| 69久久夜色精品国产69| 五月丁香综合激情六月久久| 久久精品国产乱子伦| 一级做a爰片久久毛片看看| 久久无码国产| 久久热这里只有精品在线观看| 亚洲AV伊人久久青青草原| 久久这里只有精品视频99| 久久综合九色欧美综合狠狠| 精品久久久无码中文字幕| 国产99久久九九精品无码|