• <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>
            posts - 195,  comments - 30,  trackbacks - 0

            錯誤代碼,過不了的數(shù)據(jù)14:15 10 17 16 12 1 10 20 17 19 4 5 9 5  可能解:(20 15 5 ),(19 17 4 ),( 17 12 10 1 ), ( 16 10 9 5 )
            下面的代碼“no”,因為(20 19 1),(17接下來湊不出來 )
            #include<iostream>
            #include<cstdlib>
            #include<algorithm>
            using namespace std;
             int length[21];
             int mark[21];
             bool cmp(int x,int y)
            {
                return x>y;
            }


              int  dfs(int sum,int flag,int n,int time)//´Ótime¿ªÊ¼ËÑË÷
              {
              if(sum==0)return 1;
                if(time<n)
              {
               for(int k=time;k<n;k++)
               {
                if(mark[k]<0&&sum-length[k]>=0)
                {
                 mark[k]=flag;
                 if(dfs(sum-length[k],flag,n,k+1))
                 return 1;
                 else
                 mark[k]=-1;
                   } 
               }
              }
                
             return 0;
              }
              int main()
              {
              freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
              int num,n;
             
              cin>>num;
              while(num--)
              {
              int sum=0;
              cin>>n;
              for(int k=0;k<n;k++)
              {
               cin>>length[k];
               mark[k]=-1;
               sum+=length[k];
              }
              sort(length,length+n,cmp);
              if(sum%4!=0||length[0]>sum/4)
              cout<<"no"<<endl;
              else
              {
               sum/=4;
               if(dfs(sum,1,n,0))
                {
               if(dfs(sum,2,n,0))
                      {
                 if(dfs(sum,3,n,0))
                 cout<<"yes"<<endl;
                 else
                 cout<<"no"<<endl;
                    } 
                    else
                    cout<<"no"<<endl;
                      }
                     else
                     cout<<"no"<<endl;
              }
                }
              //system("PAUSE");
              return   0;
              }
            正確的解法應當是,在一起搜索。
            下面是一段超時的代碼
            #include<iostream>
            #include<cstdlib>
            #include<algorithm>
            using namespace std;
             int length[21];
             int mark[21];
             int flag=0;
             int target;
             bool cmp(int x,int y)
            {
                return x>y;
            }

              int func(int i)
              {
              while(mark[i]>0)
              i++;
              return i;
             }
              void  dfs(int sum,int n,int time,int level)//從序號為time的開始搜索
              {
              if(flag)return ;
              if(sum==0&&level==3)
              {
              flag=1;
              return;
                 }
                 if(sum==0)
                 {
               level++;
               dfs(target,n,func(0),level);
              }
                else if(time<n)
              {
               for(int k=time;k<n;k++)
               {
                if(k>1)
                           {
                           
                            if(length[k]==length[k-1]&&!mark[k-1])
                                continue;//顯然
                           }
                            if(sum<length[n-1])  continue;//顯然
                if(mark[k]<0&&sum-length[k]>=0)
                {
                 mark[k]=1;
                 dfs(sum-length[k],n,func(k+1),level);
                 mark[k]=-1;
                   } 
               }
              }
              }
              int main()
              {
              freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
              int num,n;
             
              cin>>num;
              while(num--)
              {
              int sum=0;
              cin>>n;
              for(int k=0;k<n;k++)
              {
               cin>>length[k];
               mark[k]=-1;
               sum+=length[k];
              }
              sort(length,length+n,cmp);
              if(sum%4!=0||length[0]>sum/4)
              cout<<"no"<<endl;
              else
              {
               sum/=4;
               target=sum;
               dfs(sum,n,0,0);
                   if(flag==0)
                   cout<<"no"<<endl;
                   else
                   cout<<"yes"<<endl;
              }   
                }
              //system("PAUSE");
              return   0;
              }

            上面超時就超時原因是減枝不徹底。level標記也不太好
            決定另外爐灶,先看看別人的代碼
            #include<iostream>
            #include<algorithm>
            using namespace std;
            int s[21];
            int v[21];
            int len;
            int m;
            int dfs(int cur,int num,int beg,int fin)
            {    
             int solve(int );
             if(num==1)
              return 1;
             if(cur==len)
             {
              return solve(num-1);
             }
               for(int i=beg;i>=fin;i--)
               {
                if(!v[i]&&cur+s[i]<=len)
                {  
                 v[i]=1;
                 if(dfs(cur+s[i],num,i-1,fin))
                  return 1;
                 v[i]=0;
                }
               }
               return 0;
            }

            int solve(int edge_num)
            {   
                 int i;
              for(i=m;i>=1;i--)
               if(!v[i])
               { 
                v[i]=1;
                if(dfs( s[i],edge_num,i-1,1))
                 return 1;
                v[i]=0;
               }
             return 0;
            }

            int main()
            {
             int n;
             cin>>n;
             while(n--)
             {
              
              cin>>m;
              int i;
              int sum=0;
              for(i=1;i<=m;i++)
              {
               cin>>s[i];
               sum+=s[i];
               v[i]=0;
              }
              
              len=sum/4;
              if(4*len!=sum)
              {
               cout<<"no"<<endl;
               continue;
              }
              sort(s+1,s+m+1);
              if(s[m]>len)
              {
               cout<<"no"<<endl;
               continue;
              }
              if(solve(4))
               cout<<"yes"<<endl;
              else
               cout<<"no"<<endl;
             }
             return 0;
            }//剪枝還可以做得更好!!!
            人家的solve寫得好!!,結合dfs.

            posted on 2009-07-03 23:29 luis 閱讀(248) 評論(0)  編輯 收藏 引用 所屬分類: 搜索給我啟發(fā)題
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产午夜久久影院| 久久精品综合网| 日本道色综合久久影院| 91精品婷婷国产综合久久| 久久久久国色AV免费观看| 国色天香久久久久久久小说| 国产亚洲综合久久系列| 精品无码久久久久久久久久| 久久国产亚洲精品| 四虎国产精品免费久久久| 久久强奷乱码老熟女网站| 狠狠色丁香婷综合久久| 久久婷婷五月综合色奶水99啪| 国产精品久久久久影院嫩草| 国产精品久久久久久五月尺| 91超碰碰碰碰久久久久久综合| 久久精品国产男包| 欧美麻豆久久久久久中文| 久久精品无码一区二区三区| 久久精品国产日本波多野结衣 | 亚洲精品乱码久久久久久按摩| 久久久久国产精品| 天堂久久天堂AV色综合| 久久久久久国产精品无码下载| 久久免费99精品国产自在现线| 久久精品无码一区二区无码| 久久频这里精品99香蕉久| 国产亚洲色婷婷久久99精品91| 精品久久久久久亚洲精品 | 91精品国产91久久久久福利| 人妻丰满AV无码久久不卡| 亚洲日韩中文无码久久| 久久精品卫校国产小美女| 亚州日韩精品专区久久久| 亚洲伊人久久综合中文成人网| 久久久久久av无码免费看大片| 久久久国产精华液| 亚洲一区精品伊人久久伊人| 东方aⅴ免费观看久久av| 亚洲午夜久久久久久噜噜噜| 久久久久99精品成人片试看 |