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

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>
            欧美一区二区三区日韩视频| 欧美一区二区观看视频| 亚洲精品永久免费| 在线中文字幕一区| 日韩一区二区电影网| 午夜精品亚洲| 国产日韩欧美在线观看| 久久久久久久久久码影片| 欧美成人在线免费视频| 免费不卡在线观看| 一区二区三区av| 噜噜噜在线观看免费视频日韩 | 午夜精品久久久久久久99水蜜桃| 一区二区高清在线| 男女精品视频| 国产一级久久| 亚洲成色www久久网站| 欧美成人高清视频| 欧美亚洲免费高清在线观看| 欧美成人综合| 欧美一区二区在线看| 狠狠色2019综合网| 亚洲另类视频| 国内精品嫩模av私拍在线观看| 亚洲一区欧美一区| 亚洲欧洲精品天堂一级| 久久精品夜色噜噜亚洲a∨| 国产精品第三页| 亚洲人成小说网站色在线| 午夜精品一区二区三区在线视 | 亚洲一二三四久久| 亚洲国产成人精品女人久久久| 午夜精品美女自拍福到在线| 久久夜色撩人精品| 好男人免费精品视频| 亚洲精品久久久蜜桃| 国产一区二区三区久久悠悠色av | 一区二区三区不卡视频在线观看| 欧美91视频| 久久精品国产亚洲aⅴ| 欧美日韩另类一区| 欧美大片免费| 欧美a级理论片| 亚洲福利小视频| 亚洲欧美国产日韩中文字幕| 99视频有精品| 欧美成人一品| 免费不卡在线观看| 国产午夜亚洲精品理论片色戒| 亚洲毛片一区二区| 亚洲精品综合久久中文字幕| 亚洲欧洲免费视频| 尤物精品国产第一福利三区| 欧美中文在线观看| 亚洲丁香婷深爱综合| 欧美一区二区三区啪啪| 欧美在线视频日韩| 国产精自产拍久久久久久| 在线视频中文亚洲| 国产日韩欧美麻豆| 亚洲主播在线观看| 欧美一区=区| 久久精品国产第一区二区三区| 性xx色xx综合久久久xx| 久久精品国产亚洲高清剧情介绍| 亚洲欧美日韩一区二区三区在线| 欧美午夜不卡影院在线观看完整版免费| 亚洲色诱最新| 欧美日韩国产综合网| 亚洲三级电影在线观看 | 国产精品国产三级国产普通话99| 亚洲人成在线影院| 在线视频免费在线观看一区二区| 一区二区三区国产盗摄| 亚洲女性裸体视频| 国产精品视频福利| 久久九九全国免费精品观看| 99国产精品视频免费观看| 免费在线成人| 小辣椒精品导航| 免费成人性网站| 亚洲欧美日韩成人| 国产欧美日韩视频一区二区| 久久精品国产99| 亚洲一区二区三区在线| 国产精品综合av一区二区国产馆| 欧美国产在线电影| 一区二区高清视频在线观看| 欧美日韩色婷婷| 亚洲免费在线视频| 蜜臀久久99精品久久久久久9 | 国产精品日本一区二区| 欧美一级一区| 91久久精品国产91久久性色| 午夜精品久久| 欧美国产一区二区三区激情无套| 亚洲男人影院| 精品99视频| 亚洲在线第一页| 99视频在线观看一区三区| 国产精品久久亚洲7777| 日韩视频一区二区| 亚洲国产91色在线| 国产精品v日韩精品| 久久激情五月丁香伊人| 欧美一区二区三区视频在线观看| 在线成人激情视频| 国产精品v日韩精品| 另类av一区二区| 噜噜噜91成人网| 在线视频欧美一区| 美女久久一区| 欧美国产第一页| 一区二区亚洲欧洲国产日韩| 99热免费精品在线观看| 久久久久国产精品一区三寸| 亚洲午夜视频| 国产精品久久久久久久9999| 久久精品一区二区三区不卡牛牛| 亚洲美女诱惑| 欧美国产亚洲另类动漫| 韩国亚洲精品| 久久精品国产亚洲精品| 久久久五月婷婷| 国产一区二区中文| 国产精品av免费在线观看| 中文欧美在线视频| 亚洲欧美激情诱惑| 日韩视频一区二区三区在线播放| 欧美成人国产| 久久久久久一区二区| 午夜视频精品| 欧美ab在线视频| 亚洲国产视频一区| 欧美国产在线观看| 久久亚洲国产精品日日av夜夜| 欧美激情一区二区三区蜜桃视频| 亚洲日韩第九十九页| 欧美连裤袜在线视频| 一本不卡影院| 亚洲毛片在线观看.| 日韩一区二区福利| 日韩午夜三级在线| 久久久91精品国产| 欧美专区福利在线| 久久精品国产亚洲a| 狂野欧美一区| 亚洲午夜在线视频| 亚洲影视中文字幕| 国产一区二区三区在线观看网站 | 国产精品久久网站| 久久国产日本精品| 欧美影院久久久| 亚洲人午夜精品| 亚洲精品中文在线| 久久先锋资源| 亚洲电影专区| 欧美一区二区三区日韩视频| 欧美一区二区日韩一区二区| 久久精品国产亚洲精品| 日韩网站在线观看| 亚洲视频一区二区| 久久精品国产96久久久香蕉| 亚洲美女av电影| 国产精品亚洲综合天堂夜夜| 国产午夜精品理论片a级大结局| 欧美成人四级电影| 欧美一区1区三区3区公司| 久久久久国产精品午夜一区| 一本色道88久久加勒比精品 | 欧美一区二区三区喷汁尤物| 久久蜜桃精品| 午夜在线视频观看日韩17c| 亚洲高清视频一区二区| 一级成人国产| 91久久在线播放| 久久午夜激情| 亚洲美女av黄| 小嫩嫩精品导航| 欧美精品免费看| 国产在线播放一区二区三区| 亚洲免费观看在线视频| 欧美一区国产一区| 91久久精品国产91久久性色tv| 开元免费观看欧美电视剧网站| 亚洲欧美制服另类日韩| 久久亚洲精品网站| 中文久久精品| 这里只有精品在线播放| 亚洲毛片在线看| 久久精品欧美| 国产精品成人观看视频免费| 欧美日韩久久久久久| 欧美日韩国产精品成人| 国产亚洲欧美日韩美女| 国产欧美一区二区三区久久 | 韩国一区二区三区美女美女秀| 日韩视频在线一区二区| 农村妇女精品| 欧美jizz19hd性欧美|