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

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            PKU 1011 Sticks

            Posted on 2006-11-30 00:34 oyjpart 閱讀(4020) 評論(15)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
            這道題作的我真的是悲喜交加阿。。。做完之后。。。長舒一口氣。。推薦大家去做!!!

            Sticks
            Time Limit:1000MS? Memory Limit:10000K
            Total Submit:18973 Accepted:4421

            Description
            George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

            Input
            The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

            Output
            The output should contains the smallest possible length of original sticks, one per line.

            Sample Input

            9
            5 2 1 5 2 1 5 2 1
            4
            1 2 3 4
            0
            

            Sample Output

            6
            5 















            1。我從大到小搜索了哇 沒用。。。
            2。我想 用預先得到所有可拼湊長度來HASH 發現太大...
            3。然后我想對每個長棍分開搜索...
            4。后來我又用記錄數目的方法搜 似乎更慢...
            終于發現真正重要的剪枝!
            1.當一個正好可以填滿的時候 就不用考慮比他小的去填了
            2.一大段的第一個小段如果不成立直接返回到上一大段
            這才是重要的剪枝
            同時還有一個 要預防反復搜索同一關鍵碼 給出下面的測試數據
            64
            40 40 40 40 40 40 40 40 40 40 40 40 40
            40 40 40 40 40 40 40 40 40 40 43 42 42
            41 10 4 40 40 40 40 40 40 40 40 40 40
            40 40 40 40 40 40 40 40 40 40 40 40 40
            40 40 40 40 40 40 40 40 40 40 40 40
            0
            呵呵 其實AC的程序里面有一大部分都過不了這個數據!包括0MSAC的!

            呵呵 過了之后 心情好啊~`哈哈
            //Solution
            //by optimistic
            #include <stdio.h>
            #include <stdlib.h>
            #include <string.h>
            int nss;
            int ss[70];
            int used[70];
            int totss;
            int maxss;
            int len;
            int cmp(const void * a, const void * b)
            {
            ?return (*(int *)b) - (*(int *)a);
            }
            int search(int times, int rest, int pos)
            {
            ?int flag = 0;
            ?if(rest == len) flag = 1; //第一種剪枝
            ?int i;
            ?if(times == totss/len) return 1;
            ?for(i = pos; i<nss; i++)
            ??if(!used[i])
            ??{
            ???if(rest == ss[i])
            ???{
            ????used[i] = 1;
            ????if(search(times+1, len, 0))?return 1;
            ????used[i] = 0;
            ??? ?return 0;????????????????????? //第二種剪枝???????????????????????????????????????????????????????????????????
            ???}
            ???else if(ss[i]<rest)
            ???{
            ????used[i] = 1;
            ????if(search(times, rest-ss[i], i+1)) return 1;
            ????used[i] = 0;
            ????if(flag) return 0;
            ????while(ss[i] == ss[i+1]) i++;
            ???}
            ???else if(flag) return 0;
            ??}
            ?return 0;
            }
            int main()
            {
            //?freopen("t.in", "r", stdin);
            ?int i;
            ?while(scanf("%d", &nss), nss>0)
            ?{
            ??memset(ss, 0, sizeof(ss));
            ??totss = maxss = 0;
            ??for(i=0; i<nss; i++)
            ??{
            ???scanf("%d", &ss[i]);
            ???totss += ss[i];
            ???if(ss[i]>maxss) maxss = ss[i];
            ??}
            ??qsort(ss, 70, sizeof(ss[0]), cmp);
            ??for(i=maxss; i<=totss; i++)
            ??{
            ???if(i==totss)
            ???{printf("%d\n", totss); break;}
            ???if(totss%i==0)
            ???{?????
            ????memset(used, 0, sizeof(used));
            ????len = i;

            ????if(search(1, len, 0)) {printf("%d\n", i); break;}
            ???}
            ??}
            ?}
            ?return 0;
            }




            Feedback

            # re: PKU 1011 Sticks   回復  更多評論   

            2007-04-13 23:40 by Jun Wang
            if(search(1, len, 0)) {printf("%d\n", i); break;}
            是不是要改成 if(search(0, len, 0)) {printf("%d\n", i); break;} ??

            # re: PKU 1011 Sticks   回復  更多評論   

            2007-07-22 19:28 by Typhoooooooooooooooooooooooooooooooooon
            感謝你那兩個重要的剪枝哈

            # re: PKU 1011 Sticks   回復  更多評論   

            2007-10-24 11:00 by delguoqing
            你上面這個測試數據的ouput是多少?

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-05-04 23:46 by mango
            你測這個... 你的半天也出不來...
            64
            40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40

            40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40

            40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40

            40

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-05-05 09:02 by oyjpart
            的確啊,很強大的數據啊

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-05-05 18:42 by zoyi
            答案是454~~可是我的程序居然是wa~5555555555

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-05-05 20:10 by oyjpart
            哦?你怎么知道答案啊

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-05-06 19:43 by zoyi
            我的程序跑出來的啊~~難道你懷疑我跑的是錯誤的???哈哈@oyjpart

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-05-07 12:49 by mango
            哎......這個數據真變態...煩死了 呵呵

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-05-07 21:06 by oyjpart
            哦。。。你過題了沒

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-05-22 15:59 by zsong
            我跑出454了,很快,不過也是wa

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-08-12 20:45 by zjh777007
            誰能告訴我
            “一大段的第一個小段如果不成立直接返回到上一大段”
            什么意思?

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-08-12 20:53 by oyjpart
            現在由一個當前情況S.
            這個時候比如有一個大棍子,長度為20,現在嘗試在其中放入一個長度為5的小棍子。結果深搜得到的結果是不可行,則認為當前情況是無解的。
            因為這個5長度的小棍子放不了這個大棍子,絕對放不了任何一根大棍子。

            # re: PKU 1011 Sticks   回復  更多評論   

            2008-11-30 11:29 by abc
            #include<iostream>
            #include<string>
            #include<fstream>
            #include<vector>
            #include<ctime>
            using namespace std;
            fstream fin("e:\\office\\txt\\acmin.txt");
            int l[65];
            int s,t,min,sum=0,len;
            int max2;
            int count=0;
            int c=0;
            static int used[65];
            int search(int leni, int s){
            if(leni==0) return 100;
            t=s;
            int count=0;
            while(l[t]>leni||used[t]){
            t--;
            if(t==0){
            //break;
            return 0;
            }
            }
            used[t]=1;
            count++;
            if(l[t]<=leni){
            int se=search(leni-l[t],s-1);

            if(se>=100){
            count+=(se-100);
            //if((leni-l[t])!=0){
            //if(count<s){
            c=1;
            for(int i=1;i<=s;i++)c*=used[i];
            if(!c){
            int sea=search(len,s-1);
            if(sea>=100){
            count+=(sea-100);
            return count+100;
            }/*else{
            return 0;
            }*/
            //}
            }
            }
            /*else{
            return 0;
            }*/
            }
            count+=100;
            return count;
            }
            int main(){
            cin>>s;
            while(s){

            max2=0;
            sum=0;
            count=0;
            for(int i=0;i<65;i++)used[i]=0;
            for(int i=1;i<=s;i++){
            cin>>l[i];
            if(l[i]>max2){
            max2=l[i];
            }
            sum+=l[i];
            }
            for(int i=0;i<=s;i++){
            for(int j=0;j<s-i;j++){
            if(l[j]>l[j+1]){
            int temp=l[j];
            l[j]=l[j+1];
            l[j+1]=temp;
            }
            }
            }
            cout<<"sum"<<sum<<endl;
            for(int i=max2;i<=sum;i++){
            len=i;

            for(int j=0;j<65;j++)used[j]=0;
            if(sum%i!=0)continue;

            int k=search(i,s);

            if(k>100){

            if((k-100)==s){cout<<i<<endl;break;}
            }else{
            continue;
            }
            }
            cin>>s;
            }

            }













            # re: PKU 1011 Sticks   回復  更多評論   

            2008-11-30 11:30 by abc
            各位高手幫忙看一下上面的程序有什么錯誤,萬分感激!
            久久久久亚洲AV成人网人人网站| | 无码久久精品国产亚洲Av影片| 久久青青草视频| 亚洲AV乱码久久精品蜜桃| 精品久久久久久成人AV| 91亚洲国产成人久久精品| 日本加勒比久久精品| 国产综合久久久久| 伊色综合久久之综合久久| 久久久久久免费一区二区三区| 久久久久亚洲AV片无码下载蜜桃| 国产成人精品久久免费动漫| 漂亮人妻被中出中文字幕久久| 一本久久久久久久| 久久亚洲精精品中文字幕| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 欧美伊人久久大香线蕉综合69| 99精品久久精品一区二区| 久久精品无码一区二区日韩AV| 久久亚洲精品无码AV红樱桃| 久久综合色老色| 日韩中文久久| 亚洲国产一成久久精品国产成人综合 | 久久久精品午夜免费不卡| 精品无码久久久久国产动漫3d | 99久久无色码中文字幕| 色综合久久久久无码专区| 久久久久久伊人高潮影院| 无码国内精品久久人妻麻豆按摩| 99久久国产主播综合精品| 国产一区二区精品久久岳| 九九热久久免费视频| 国内精品久久久久久久涩爱| 久久精品国产99久久丝袜| 久久综合亚洲色HEZYO国产| 免费一级做a爰片久久毛片潮| 久久精品中文字幕一区| 亚洲国产精品无码久久九九| 欧美国产成人久久精品| 久久天天躁狠狠躁夜夜网站|