• <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)  編輯 收藏 引用 所屬分類: 搜索給我啟發題
            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产成人久久精品99 | 噜噜噜色噜噜噜久久| 91精品久久久久久无码| 国产精品嫩草影院久久| 久久91精品国产91| 国产精品久久久久无码av| 国内精品久久久久久99蜜桃 | 狠狠88综合久久久久综合网| 久久99精品久久久久婷婷| 九九久久精品国产| 中文字幕热久久久久久久| 精品久久久久久国产免费了| 狠狠色噜噜色狠狠狠综合久久| 久久精品草草草| 久久婷婷五月综合97色一本一本| 久久成人18免费网站| 99久久夜色精品国产网站| 久久99热这里只有精品国产| 乱亲女H秽乱长久久久| 色婷婷综合久久久久中文字幕| 99久久国语露脸精品国产| 久久精品国产男包| 免费一级欧美大片久久网| 国产精品久久久久久吹潮| 狠狠色综合网站久久久久久久高清 | 亚洲v国产v天堂a无码久久| 久久伊人精品青青草原高清| 无码国内精品久久人妻蜜桃 | 日韩久久久久久中文人妻| 亚洲国产成人乱码精品女人久久久不卡 | 伊人久久大香线蕉综合Av| 一本综合久久国产二区| 日本加勒比久久精品| 久久精品国产只有精品66| 狠狠久久综合| 久久久久久国产a免费观看不卡| 国产毛片久久久久久国产毛片| 国产精品综合久久第一页| 国产亚洲精午夜久久久久久| 精品国产一区二区三区久久蜜臀| 国産精品久久久久久久|