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

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            一本色道久久HEZYO无码| 91精品观看91久久久久久| 欧美大战日韩91综合一区婷婷久久青草 | 94久久国产乱子伦精品免费 | 青草影院天堂男人久久| 久久男人AV资源网站| 麻豆精品久久久久久久99蜜桃| 色欲久久久天天天综合网| 国产一区二区精品久久| 一本一道久久a久久精品综合| 少妇久久久久久久久久| 欧美午夜精品久久久久久浪潮| 欧美久久综合九色综合| 久久99国产乱子伦精品免费| 久久久久这里只有精品| 韩国免费A级毛片久久| 欧美精品乱码99久久蜜桃| 亚洲国产精久久久久久久| 日本欧美久久久久免费播放网| 91麻精品国产91久久久久| 久久久久高潮毛片免费全部播放| 久久人人超碰精品CAOPOREN| 国内精品久久国产大陆| 久久国产精品77777| 久久精品国产久精国产一老狼| 久久久黄片| 国产日韩久久免费影院| 国内精品久久久久久野外| 久久人人爽人人爽人人AV| 中文精品99久久国产 | 欧美一级久久久久久久大片| 66精品综合久久久久久久| www久久久天天com| 99999久久久久久亚洲| 69国产成人综合久久精品| 午夜天堂精品久久久久| 亚洲精品午夜国产VA久久成人 | 午夜精品久久久久久久| 久久婷婷五月综合97色一本一本| 日产精品99久久久久久| 精品久久久久久久|