青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(4029) 評論(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
各位高手幫忙看一下上面的程序有什么錯誤,萬分感激!
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品久久久久久久久免费樱桃 | 99国产精品国产精品毛片| 亚洲免费一级电影| 亚洲第一区中文99精品| 午夜精品久久99蜜桃的功能介绍| 欧美日韩在线免费视频| 精品福利电影| 久久精品欧美日韩| 午夜精品一区二区三区在线播放| 欧美视频在线观看免费| 国产精品九九| 亚洲欧美日韩国产一区| 一区二区三区高清在线| 欧美日韩日本视频| 国产视频一区在线观看一区免费| 亚洲在线免费观看| 一区二区三区日韩精品| 欧美主播一区二区三区| 国产区亚洲区欧美区| 午夜激情一区| 亚洲欧美日韩精品久久久| 久久精品首页| 亚洲韩国精品一区| 欧美国产另类| 久久免费精品日本久久中文字幕| 亚洲电影第1页| 亚洲欧洲精品一区二区三区波多野1战4 | 激情欧美日韩| 亚洲精选在线| 亚洲精品欧美一区二区三区| 欧美日本中文| 亚洲免费视频网站| 久久国产99| 亚洲全黄一级网站| 亚洲毛片av| 国产日韩欧美成人| 欧美成人在线网站| 欧美日韩三级电影在线| 欧美一区二区高清在线观看| 午夜一区不卡| 在线成人性视频| 日韩午夜激情av| 国产一级一区二区| 欧美国产一区二区| 国产精品成人国产乱一区| 久久成人综合视频| 蜜桃av综合| 欧美一级夜夜爽| 美国十次了思思久久精品导航| 亚洲伊人一本大道中文字幕| 久久精品视频一| 国产精品99久久久久久有的能看 | 国产精品第一区| 亚洲国产精品久久久久久女王| 一本一本久久a久久精品牛牛影视| 欧美激情欧美激情在线五月| 男人插女人欧美| 在线观看亚洲精品视频| 久久久国产视频91| 猫咪成人在线观看| 韩日精品视频一区| 久久久一本精品99久久精品66| 久久丁香综合五月国产三级网站| 国产精品久久久久久久app| 亚洲麻豆视频| 亚洲欧美制服另类日韩| 国产欧美大片| 欧美影院成人| 欧美ed2k| 99精品欧美一区二区蜜桃免费| 欧美黄色网络| 中日韩美女免费视频网站在线观看 | 久久精品国产99| 久久亚洲高清| 亚洲国产综合91精品麻豆| 欧美激情综合| 一区二区三区国产精华| 欧美在线电影| 亚洲激情国产| 欧美性事在线| 久久精品系列| 亚洲精品久久久久久久久| 亚洲深夜av| 国产在线播精品第三| 欧美成人精品在线播放| 99人久久精品视频最新地址| 欧美一区二区三区男人的天堂| 影音先锋欧美精品| 欧美日本国产精品| 午夜国产一区| 亚洲国产精品一区在线观看不卡 | 久久婷婷av| 一本色道久久精品| 国产亚洲欧美日韩在线一区| 你懂的视频欧美| 亚洲一二三区在线| 美女国内精品自产拍在线播放| 亚洲免费观看视频| 国产自产精品| 欧美三级欧美一级| 久久亚洲影音av资源网| 亚洲视频在线观看网站| 欧美va天堂在线| 亚洲欧美一区二区激情| 亚洲人精品午夜| 国产亚洲精品一区二555| 欧美大片免费观看在线观看网站推荐| 在线午夜精品自拍| 欧美国产亚洲另类动漫| 久久精品国产在热久久 | 国产精品普通话对白| 欧美91大片| 久久九九热免费视频| 一区二区三区国产在线观看| 久久一区二区三区国产精品 | 欧美国产视频一区二区| 久久久精品国产一区二区三区 | 欧美在线高清视频| 亚洲午夜av在线| 亚洲精品久久久久久久久| 国产网站欧美日韩免费精品在线观看| 欧美日本韩国一区二区三区| 男男成人高潮片免费网站| 久久天堂国产精品| 欧美在线观看www| 亚洲欧美成人精品| 亚洲午夜久久久久久久久电影网| 亚洲欧洲日本一区二区三区| 欧美国产日本高清在线| 免费看的黄色欧美网站| 久久综合九九| 久久久久.com| 久久资源在线| 久久精品视频在线免费观看| 香蕉av777xxx色综合一区| 亚洲视频在线视频| 99re6热只有精品免费观看| 亚洲大胆人体在线| 亚洲国产专区| 亚洲精品乱码视频| 亚洲精品一区二区三区蜜桃久 | 欧美激情视频免费观看| 欧美大尺度在线| 欧美区日韩区| 欧美日韩一区二区三区| 国产精品豆花视频| 国产麻豆成人精品| 国产日韩一区在线| 国模精品一区二区三区| 国产综合色产| 亚洲国产欧美日韩精品| 日韩午夜剧场| 亚洲一区二区精品| 欧美一区激情视频在线观看| 久久精品成人一区二区三区蜜臀| 久久天天狠狠| 欧美激情第五页| 日韩一二三在线视频播| 亚洲中字黄色| 久久久久久69| 欧美日韩国产va另类| 国产精品久久久久久久久久妞妞| 国产一区二区av| 亚洲激情小视频| 亚洲欧美偷拍卡通变态| 久久综合九色| 一本色道**综合亚洲精品蜜桃冫| 亚洲免费视频一区二区| 米奇777超碰欧美日韩亚洲| 欧美视频中文字幕在线| 国产农村妇女毛片精品久久莱园子| 国外成人在线| 亚洲一区免费网站| 老司机精品视频网站| 亚洲精选91| 欧美专区在线| 欧美日韩免费观看一区二区三区 | 欧美精品久久久久a| 国产欧美日韩精品专区| 亚洲全部视频| 久久精品女人天堂| 亚洲免费电影在线观看| 久久精品首页| 国产精品日韩欧美一区二区三区| 永久555www成人免费| 亚洲一区二区三区四区中文| 欧美成人午夜视频| 午夜精品一区二区三区在线| 欧美精品一区二区三区高清aⅴ| 国产欧美日韩一区| 亚洲视频网在线直播| 欧美成人午夜视频| 欧美亚洲免费高清在线观看| 欧美日韩在线电影| 亚洲欧洲一区二区三区| 卡一卡二国产精品| 欧美一区二区啪啪| 国产精品免费一区二区三区在线观看| 亚洲片在线资源| 你懂的视频欧美|