• <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
            Sum It Up
            Status In/Out TIME Limit MEMORY Limit Submit Times Solved Users JUDGE TYPE
            stdin/stdout 3s 8192K 424 182 Standard

            Given a specifie d total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.

            Input

            The input file will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers . If n = 0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.

            Output

            For each test case, first output a line containing `Sums of ', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line `NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distinct; the same sum cannot appear twice.

            Sample Input

            4 6 4 3 2 2 1 1
            5 3 2 1 1
            400 12 50 50 50 50 50 50 25 25 25 25 25 25
            0 0
            

            Sample Output

            Sums of 4:
            4
            3+1
            2+2
            2+1+1
            Sums of 5:
            NONE
            Sums of 400:
            50+50+50+50+50+50+25+25+25+25
            50+50+50+50+50+25+25+25+25+25+25
            
            #include<iostream>
            #include
            <cstdlib>
            #include
            <memory>
            using namespace std;
            int mount;
            int l;
            int a[12][2];
            int mark;
              
            void output()
              {
                mark
            ++;   
                
            int temp[12];   
                
            int flag=0;
                
            for(int i=0;i<mount;i++)
                {  
                 
            if(a[i][1])
                {
                  
            if(flag==0)
                  flag
            ++;
                  
            else
                  cout
            <<"+";
                 cout
            <<a[i][0];
                 }                          
                }          
                 cout
            <<endl;            
              }
              
            void dfs(int sum,int nowv,int pre)
              {
                   
            int value;
                   
            if(nowv==sum)
                   {
                      output();         
                   }
                   
            else
                   {
                       
            for(int j=pre+1;j<mount;j++)
                       {
                         value
            =a[j][0];      
                         
            if(nowv+value<=sum&&value!=l)
                         { 
                         a[j][
            1]=1;                                                       
                         dfs(sum,nowv
            +value,j);
                         a[j][
            1]=0;
                         }   
                       }
                   }
                   
            if(pre!=-1)
                   l
            =a[pre][0];
              }
              
            int main()
              {
              
            //freopen("s.txt","r",stdin);
              
            //freopen("key.txt","w",stdout);
              int sum,i,j;
              cin
            >>sum>>mount;
              
            while(sum!=0)
              {           
                
            for(i=0;i<mount;i++)
                {
                   cin
            >>a[i][0];
                   a[i][
            1]=0;      
                }
                
                mark
            =0;
                l
            =0;
                cout
            <<"Sums of "<<sum<<":"<<endl;
                dfs(sum,
            0,-1);
                
            if(mark==0)
                cout
            <<"NONE"<<endl;         
                cin
            >>sum>>mount;         
              }
              
            //system("PAUSE");
              return 0;
              }

             

            難點(diǎn):1,有序遞減,這個(gè)好處理,只需在向前推時(shí)dfs(i)for(int j=i+1...)即可
                        2,去掉無(wú)效的重復(fù)搜索,這個(gè)煩一點(diǎn),比如和為11時(shí),序列為6,6,6,2,2,2,1,6+2+2+1顯然是可以的,但是6+6不可以。6+6+6更不可以
            我們可以這樣想,如果順著往前推是,如果不超過(guò)范圍,比如6+2+取后一個(gè)數(shù)時(shí),2可以取,但是6+6,超過(guò)11,要回溯的時(shí)候,記錄下此時(shí)的6,用下面的代碼

            if(pre!=-1)
                   l=a[pre][0];

            在比較if(nowv+value<=sum&&value!=l)此時(shí)不符合,下一個(gè)6取不到了!避免了重復(fù)。
            posted on 2009-05-14 16:32 luis 閱讀(471) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 搜索給我啟發(fā)題
            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久午夜无码鲁丝片| 无码8090精品久久一区 | 久久国产成人午夜aⅴ影院 | 婷婷久久香蕉五月综合加勒比| 亚洲精品乱码久久久久久按摩| 久久精品免费一区二区三区| 国产精品久久久99| 久久99久久99精品免视看动漫| 狼狼综合久久久久综合网| 久久精品国产亚洲av瑜伽| 一本久久a久久精品vr综合| 91久久国产视频| 亚洲午夜久久久久久久久电影网| 一本久久久久久久| 婷婷久久久亚洲欧洲日产国码AV | 久久综合亚洲鲁鲁五月天| 久久91精品国产91久久小草| 亚洲AV无码久久| 久久精品国产99久久丝袜| 国产精品久久久久…| AV无码久久久久不卡蜜桃| 日本国产精品久久| 国产精久久一区二区三区| 99国产欧美精品久久久蜜芽| 亚洲综合久久久| 亚洲精品乱码久久久久久不卡| 国产精品久久国产精麻豆99网站 | 久久婷婷五月综合色高清| 污污内射久久一区二区欧美日韩| 99久久精品无码一区二区毛片| 亚洲AV无一区二区三区久久| 囯产极品美女高潮无套久久久| 亚洲国产婷婷香蕉久久久久久| 国产香蕉97碰碰久久人人| 很黄很污的网站久久mimi色| 久久香蕉一级毛片| 99久久精品这里只有精品| 精品久久久无码中文字幕天天| 97精品国产97久久久久久免费| 97久久精品人人做人人爽| 久久996热精品xxxx|