• <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算法程序設(shè)計(jì)空間

            // 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) 評(píng)論(15)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
            這道題作的我真的是悲喜交加阿。。。做完之后。。。長(zhǎng)舒一口氣。。推薦大家去做!!!

            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。我從大到小搜索了哇 沒(méi)用。。。
            2。我想 用預(yù)先得到所有可拼湊長(zhǎng)度來(lái)HASH 發(fā)現(xiàn)太大...
            3。然后我想對(duì)每個(gè)長(zhǎng)棍分開(kāi)搜索...
            4。后來(lái)我又用記錄數(shù)目的方法搜 似乎更慢...
            終于發(fā)現(xiàn)真正重要的剪枝!
            1.當(dāng)一個(gè)正好可以填滿的時(shí)候 就不用考慮比他小的去填了
            2.一大段的第一個(gè)小段如果不成立直接返回到上一大段
            這才是重要的剪枝
            同時(shí)還有一個(gè) 要預(yù)防反復(fù)搜索同一關(guān)鍵碼 給出下面的測(cè)試數(shù)據(jù)
            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
            呵呵 其實(shí)AC的程序里面有一大部分都過(guò)不了這個(gè)數(shù)據(jù)!包括0MSAC的!

            呵呵 過(guò)了之后 心情好啊~`哈哈
            //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   回復(fù)  更多評(píng)論   

            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   回復(fù)  更多評(píng)論   

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

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

            2007-10-24 11:00 by delguoqing
            你上面這個(gè)測(cè)試數(shù)據(jù)的ouput是多少?

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

            2008-05-04 23:46 by mango
            你測(cè)這個(gè)... 你的半天也出不來(lái)...
            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   回復(fù)  更多評(píng)論   

            2008-05-05 09:02 by oyjpart
            的確啊,很強(qiáng)大的數(shù)據(jù)啊

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

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

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

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

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

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

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

            2008-05-07 12:49 by mango
            哎......這個(gè)數(shù)據(jù)真變態(tài)...煩死了 呵呵

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

            2008-05-07 21:06 by oyjpart
            哦。。。你過(guò)題了沒(méi)

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

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

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

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

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

            2008-08-12 20:53 by oyjpart
            現(xiàn)在由一個(gè)當(dāng)前情況S.
            這個(gè)時(shí)候比如有一個(gè)大棍子,長(zhǎng)度為20,現(xiàn)在嘗試在其中放入一個(gè)長(zhǎng)度為5的小棍子。結(jié)果深搜得到的結(jié)果是不可行,則認(rèn)為當(dāng)前情況是無(wú)解的。
            因?yàn)檫@個(gè)5長(zhǎng)度的小棍子放不了這個(gè)大棍子,絕對(duì)放不了任何一根大棍子。

            # re: PKU 1011 Sticks   回復(fù)  更多評(píng)論   

            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   回復(fù)  更多評(píng)論   

            2008-11-30 11:30 by abc
            各位高手幫忙看一下上面的程序有什么錯(cuò)誤,萬(wàn)分感激!
            日韩一区二区三区视频久久| 久久精品国产亚洲欧美| 久久青青草原国产精品免费| 久久精品一区二区影院| 伊人久久成人成综合网222| 国产亚洲综合久久系列| 伊人久久免费视频| 欧美精品九九99久久在观看| 久久er99热精品一区二区| 亚洲精品99久久久久中文字幕| 2020久久精品亚洲热综合一本| 青青青伊人色综合久久| 久久91精品国产91久| 久久亚洲国产中v天仙www | 久久夜色精品国产亚洲| 亚洲午夜久久久| 精品久久777| 色偷偷91久久综合噜噜噜噜| 91精品国产高清久久久久久io| 国产999精品久久久久久| 国产综合久久久久| 亚洲国产成人久久笫一页| 久久电影网一区| 午夜天堂精品久久久久| 精品久久久无码21p发布| 亚洲国产精品无码久久青草| 亚洲国产天堂久久综合网站| 久久久女人与动物群交毛片| 久久精品国产亚洲αv忘忧草| 国产精久久一区二区三区| 97久久天天综合色天天综合色hd| 天堂无码久久综合东京热| 国产午夜精品久久久久九九电影| 国产精品亚洲美女久久久| 国产精品久久久久久影院| 久久精品aⅴ无码中文字字幕不卡| 亚洲精品乱码久久久久久自慰| 精品久久久久久久国产潘金莲| 一级做a爰片久久毛片看看| 亚洲国产成人久久综合野外| 最新久久免费视频|