• <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)分感激!
            亚洲精品无码久久久久| 亚洲精品高清久久| 婷婷久久久亚洲欧洲日产国码AV | 欧美一级久久久久久久大片| 伊人久久五月天| 久久国产精品久久| 日产精品久久久久久久| 久久亚洲精品视频| 色偷偷88888欧美精品久久久| 97超级碰碰碰碰久久久久| 亚洲精品美女久久777777| 亚洲欧美日韩精品久久| 欧洲成人午夜精品无码区久久 | 久久人人爽人人爽AV片| 久久婷婷激情综合色综合俺也去| 91精品免费久久久久久久久| 一本一本久久A久久综合精品| 久久精品国产亚洲精品| 国内精品九九久久久精品| 久久无码AV一区二区三区| 久久99精品久久久久久齐齐| 国产精品久久久久…| 久久香蕉超碰97国产精品| 久久午夜福利无码1000合集| 久久久久女教师免费一区| 国产综合免费精品久久久| 婷婷综合久久狠狠色99h| 久久91精品国产91久久小草| 狠狠88综合久久久久综合网| 久久久久久国产精品美女| 久久夜色精品国产噜噜亚洲a| 午夜福利91久久福利| 亚洲精品NV久久久久久久久久| 国产精品成人99久久久久| 国产午夜精品久久久久九九| 国产激情久久久久影院老熟女免费| 国产成人综合久久综合| 国内精品久久久久久久亚洲| 精品无码人妻久久久久久| 无码人妻少妇久久中文字幕| 7777精品伊人久久久大香线蕉|