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

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>
            国产精品多人| 欧美国产在线观看| 国产视频精品网| 久久精品人人做人人综合 | 亚洲无限乱码一二三四麻| 欧美国产日韩在线| 一卡二卡3卡四卡高清精品视频| 在线观看视频日韩| 欧美顶级艳妇交换群宴| 欧美日一区二区在线观看| 午夜精品久久久久久久99水蜜桃 | 久久精品国产欧美激情| 久久久久久91香蕉国产| 亚洲国产午夜| 这里只有精品丝袜| 在线观看日韩欧美| 亚洲午夜一级| 亚洲国产精品电影在线观看| 亚洲久色影视| 好吊成人免视频| 99视频在线精品国自产拍免费观看| 欧美一级播放| 亚洲精品综合在线| 亚洲欧美在线aaa| 亚洲电影免费观看高清完整版在线观看 | 欧美日韩午夜视频在线观看| 欧美一级网站| 欧美久久视频| 巨乳诱惑日韩免费av| 欧美日韩在线一二三| 蜜臀久久99精品久久久久久9| 亚洲欧美电影在线观看| 亚洲国产精品va在线看黑人动漫| 久久久精品国产免费观看同学 | 久久久久久久波多野高潮日日 | 亚洲精品一区久久久久久| 国产区二精品视| 一本色道久久综合亚洲精品不卡 | 老司机精品导航| 亚洲欧美日韩久久精品| 欧美激情免费在线| 免费观看成人鲁鲁鲁鲁鲁视频| 久久精品国产91精品亚洲| 亚洲午夜精品网| 欧美大片va欧美在线播放| 久久久久久高潮国产精品视| 国产精品三级视频| 亚洲无毛电影| 亚洲中字在线| 欧美性猛片xxxx免费看久爱| 亚洲人线精品午夜| 亚洲动漫精品| 久久综合五月| 久久字幕精品一区| 国产日韩三区| 欧美一区国产二区| 久久精品人人爽| 国产日产欧美a一级在线| 中日韩美女免费视频网址在线观看| 国产精品免费在线| 99成人在线| 亚洲视频观看| 欧美午夜精品一区| 亚洲一区二区三区午夜| 先锋a资源在线看亚洲| 国产精品视频专区| 亚洲欧美日韩在线播放| 久久国产精品久久久| 国产一区二区视频在线观看| 欧美诱惑福利视频| 欧美成人高清视频| 亚洲精选视频在线| 欧美日韩你懂的| 亚洲一级网站| 久久亚洲欧美| 亚洲理论在线| 欧美亚男人的天堂| 欧美一区二区三区四区在线观看地址| 一区二区在线观看av| 久久亚洲国产精品一区二区| 欧美成人资源网| 一区二区欧美在线| 国产精品丝袜xxxxxxx| 久久狠狠婷婷| 亚洲欧洲在线一区| 小嫩嫩精品导航| 在线精品视频一区二区三四| 欧美华人在线视频| 午夜精品亚洲| 亚洲第一视频| 欧美一区二区三区在线看| 伊人久久大香线蕉综合热线| 欧美久久久久久| 欧美一区免费视频| 亚洲欧洲日本专区| 久久久精品网| 一区二区三区www| 韩国自拍一区| 欧美特黄视频| 六月婷婷一区| 午夜精品久久久久久久男人的天堂| 亚洲另类自拍| 国产日韩欧美中文| 欧美黄免费看| 欧美在线在线| 亚洲视频狠狠| 亚洲国产精品久久久久婷婷老年| 一区二区在线看| 国产精品海角社区在线观看| 美女网站久久| 欧美一区二区三区男人的天堂| 亚洲一区在线免费| 亚洲日本成人| 韩国精品一区二区三区| 欧美日韩国产成人高清视频| 久久久久久久综合色一本| 亚洲图片你懂的| 日韩视频免费在线观看| 米奇777超碰欧美日韩亚洲| 亚洲制服av| 夜色激情一区二区| 91久久在线视频| 永久久久久久| 国产欧美丝祙| 国产精品伦理| 国产精品成人国产乱一区| 欧美久久久久久久久久| 美女网站久久| 免播放器亚洲一区| 久久美女艺术照精彩视频福利播放| 欧美va亚洲va香蕉在线| 久久亚洲精品视频| 久久精品国产欧美激情| 亚洲在线国产日韩欧美| 亚洲视频在线二区| 在线视频精品| 亚洲私拍自拍| 亚洲综合清纯丝袜自拍| 亚洲欧美日韩国产中文| 午夜日韩福利| 久久精品一区二区国产| 久久久久国产一区二区| 久久久国产精品一区| 久久蜜桃av一区精品变态类天堂| 伊人成年综合电影网| 国产主播一区二区三区| 激情亚洲网站| 尤物在线观看一区| 亚洲精品黄网在线观看| 99精品欧美一区二区三区综合在线 | 欧美国产成人在线| 亚洲黄色影院| 日韩午夜在线播放| 午夜精品短视频| 久久久久久久久久久久久9999| 亚洲第一色在线| 亚洲国产精品一区二区久| 亚洲精品久久久久中文字幕欢迎你| 欧美中文字幕在线播放| 欧美一区二区私人影院日本| 久久久久一区二区| 欧美国产在线视频| 一区二区av在线| 久久激情视频| 欧美精品一区二区三| 国产精品丝袜久久久久久app | 中文国产亚洲喷潮| 欧美一级精品大片| 欧美jizzhd精品欧美巨大免费| 午夜欧美电影在线观看| 蜜桃av综合| 国产精品美女久久久浪潮软件| 蜜桃久久精品一区二区| 欧美日韩一级黄| 狠狠色噜噜狠狠色综合久 | 久久―日本道色综合久久| 欧美精品一区二区三| 国产偷国产偷亚洲高清97cao| 欧美日韩精品一区| 国产一区二区三区的电影| 亚洲精品影视在线观看| 欧美亚洲综合久久| 亚洲精品裸体| 久久久久99精品国产片| 欧美视频精品在线| 亚洲激情电影中文字幕| 欧美专区日韩视频| 日韩一区二区免费高清| 久久夜色精品国产亚洲aⅴ | 一本到高清视频免费精品| 久久九九精品| 国产伦精品一区二区三区高清版| 国产精品va在线播放| 在线看欧美视频| 久久精品国产欧美亚洲人人爽| 欧美一区二区日韩| 亚洲国产综合在线看不卡| 久久九九精品99国产精品| 国产精品网站一区| 亚洲一区999|