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

             

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

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

            在比較if(nowv+value<=sum&&value!=l)此時不符合,下一個6取不到了!避免了重復。
            posted on 2009-05-14 16:32 luis 閱讀(471) 評論(0)  編輯 收藏 引用 所屬分類: 搜索給我啟發題
            <2011年3月>
            272812345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            偷偷做久久久久网站| 久久亚洲AV成人无码电影| 色综合久久综合中文综合网 | 亚洲∧v久久久无码精品| 国色天香久久久久久久小说| AV无码久久久久不卡网站下载| 狠狠色丁香婷综合久久| 亚洲精品tv久久久久久久久久| 狠狠色噜噜色狠狠狠综合久久| 国产成人久久精品区一区二区| 久久久久亚洲AV无码去区首| 久久久久久国产精品免费无码| 亚洲国产精品久久久久婷婷老年| 狠狠色丁香婷婷久久综合| 国产美女久久久| 亚洲精品乱码久久久久久蜜桃不卡 | 四虎影视久久久免费观看| av国内精品久久久久影院| 久久大香萑太香蕉av| 品成人欧美大片久久国产欧美...| 久久综合九色综合网站| 亚洲伊人久久综合影院| 精品人妻伦九区久久AAA片69| 色欲av伊人久久大香线蕉影院| 亚洲欧美精品一区久久中文字幕| 国内精品免费久久影院| 国产精品久久国产精麻豆99网站| 国产亚洲精久久久久久无码77777| 久久久久久av无码免费看大片| 久久97久久97精品免视看| 久久精品99久久香蕉国产色戒 | 久久93精品国产91久久综合| 久久se精品一区二区| 狠狠色丁香婷综合久久| 久久99精品国产99久久6男男| 久久亚洲AV无码精品色午夜 | 久久精品国产精品亚洲下载| 国产ww久久久久久久久久| 久久青草国产精品一区| 久久精品国产99国产精品澳门 | 久久久久亚洲AV无码去区首|