• <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>

            infinity

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              36 隨筆 :: 0 文章 :: 25 評論 :: 0 Trackbacks
            http://acm.pku.edu.cn/JudgeOnline/problem?id=2362

            很好很經典的深搜題,減枝不好很容易TLE,注意搜索順序。先從大到小排序。這題跟1011差不多
            1011黑書上有講。最重要的減枝就是不能重復搜索,所以函數是int solve(int unused,int start,int left)
            start就是拼當前這一條邊的時候從那跟開始搜起。left表示當前這條邊還剩多少拼完

            Source Code

            Problem: 2362 User: lovecanon
            Memory: 204K Time: 16MS
            Language: C Result: Accepted
             
            
            #include<stdio.h>
            #include
            <string.h>
            #include
            <stdlib.h>

            int len[21];
            int used[21];
            int n;
            int side;
            int start;

            int cmp(const void *a,const void *b)
            {
                
            return *(int *)b-*(int *)a;
            }

            int solve(int unused,int start,int left)
            {
                
            int i;
                
            if(unused==0&&left==0)  return 1;
                
            if(unused==0return 0;

                
            if(left==0
                {
                    left
            =side;
                    
            for(i=1;i<=n&&used[i];i++)
                        
            if(solve(unused,i,side)) return 1;
                }
                
                
            for(i=start;i<=n;i++)
                {
                    
            if(!used[i]&&len[i]<=left)
                    {
                        
            if(i>1)
                        {
                            
                            
            if(len[i]==len[i-1]&&!used[i-1])
                                
            continue;
                        }
                        
            if(left<len[n])  continue;
                        used[i]
            =1;

                        
            if(solve(unused-1,i,left-len[i])) return 1;
                        used[i]
            =0;
                        
            if(len[i]==left||left==side)  return 0;
                    }

                }
                
            return 0;
            }
             
            int main()
            {
                
            int T,sum,i;
                scanf(
            "%d",&T);
                
            while(T--)
                {
                    sum
            =0;
                    scanf(
            "%d",&n);
                    len[
            0]=0x7fffffff;
                    
            for(i=1;i<=n;i++)
                    {
                        scanf(
            "%d",&len[i]);
                        sum
            +=len[i];
                    }
                    
            if(sum%4) printf("no\n");
                    
            else
                    {
                        side
            =sum/4;
                        memset(used,
            0,sizeof(used));
                        qsort(len,n
            +1,sizeof(len[0]),cmp);

                        
            if(len[1]>side) printf("no\n");
                        
            else if(solve(n,1,side))   printf("yes\n");
                        
            else printf("no\n");
                    }
                }
                
            return 0;
            }

            posted on 2008-09-20 04:46 infinity 閱讀(1058) 評論(1)  編輯 收藏 引用 所屬分類: acm

            評論

            # re: poj 2362 2009-07-05 09:36 luis
            問一下牛人這句if(len[i]==left||left==side) return 0;的原理是什么?
              回復  更多評論
              

            国产色综合久久无码有码| 中文字幕无码免费久久| 怡红院日本一道日本久久 | 国产午夜精品久久久久九九电影| 欧美一区二区精品久久| 久久996热精品xxxx| 久久免费大片| 91精品国产高清久久久久久国产嫩草 | 久久精品国产福利国产秒| 久久一区二区免费播放| 亚洲天堂久久久| 欧美大香线蕉线伊人久久| 久久精品国产精品亚洲艾草网美妙| 亚洲精品蜜桃久久久久久| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 久久超碰97人人做人人爱| 久久精品夜色噜噜亚洲A∨| 久久综合九色综合欧美就去吻| 无码人妻久久一区二区三区蜜桃| 伊人久久综在合线亚洲2019| 久久综合五月丁香久久激情| 婷婷伊人久久大香线蕉AV| 久久国产一片免费观看| 亚洲国产欧洲综合997久久| 成人午夜精品久久久久久久小说 | 久久久久亚洲AV无码观看| 青青热久久国产久精品 | 久久天天躁狠狠躁夜夜躁2014| 麻豆一区二区99久久久久| 狠狠色综合网站久久久久久久| 欧美激情一区二区久久久| 色综合久久精品中文字幕首页| 波多野结衣久久| 国产精品青草久久久久福利99 | 亚洲精品无码久久久久去q| 99久久精品免费看国产一区二区三区| 中文成人无码精品久久久不卡| 久久噜噜久久久精品66| 69久久精品无码一区二区| 97久久精品无码一区二区| 99久久香蕉国产线看观香|