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

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精品欧美一区二区三区综合在线| 久久久久久网站| 国模叶桐国产精品一区| 久久久久一区二区三区四区| 午夜精品在线视频| 国产日韩欧美电影在线观看| 久久av在线| 欧美一区二区三区在线视频 | 亚洲成人资源网| 久久蜜臀精品av| 久久久五月婷婷| 亚洲激情一区二区| 一区二区高清在线观看| 国产精品免费视频观看| 香蕉免费一区二区三区在线观看| 小黄鸭精品密入口导航| 国产精品综合久久久| 久久精品国语| 欧美高清视频www夜色资源网| 亚洲美女av电影| 麻豆精品传媒视频| 久久在线免费| 一区二区三区偷拍| 午夜欧美大尺度福利影院在线看| 国产亚洲欧美日韩精品| 欧美**人妖| 欧美性大战xxxxx久久久| 午夜久久福利| 久久亚洲图片| 亚洲男女自偷自拍| 久久久成人精品| 亚洲大片av| 欧美高清在线视频| 国产精品视频不卡| 香蕉av777xxx色综合一区| 久久精视频免费在线久久完整在线看 | 亚洲在线观看视频网站| 欧美在线免费视屏| 亚洲精品午夜精品| 亚洲已满18点击进入久久| 亚洲国产高清在线观看视频| 久久综合成人精品亚洲另类欧美| 欧美精品一级| 久久精品欧洲| 国产精品成人午夜| 亚洲第一精品在线| 国产一区亚洲| 99国产欧美久久久精品| 亚洲国产精品成人综合色在线婷婷| 夜夜爽av福利精品导航| 亚洲国产精品一区制服丝袜 | 欧美在线地址| 国产精品福利影院| 亚洲国产日本| 亚洲国产精品传媒在线观看 | 久久午夜国产精品| 国产精品高清网站| 亚洲激情小视频| 亚洲电影毛片| 亚洲午夜电影| 亚洲综合色网站| 美女性感视频久久久| 久久久女女女女999久久| 欧美人与禽性xxxxx杂性| 欧美激情按摩| 国产在线播放一区二区三区| 亚洲午夜激情网站| 亚洲欧洲在线播放| 亚洲欧美一区二区在线观看| 亚洲亚洲精品三区日韩精品在线视频| 久久国产精品电影| 亚洲女同同性videoxma| 麻豆亚洲精品| 免费在线观看一区二区| 黄色一区二区三区四区| 久久精品国产精品| 久久综合色综合88| 国模精品娜娜一二三区| 久久精品国产69国产精品亚洲| 久久国产精品久久国产精品| 国产欧美一区二区白浆黑人| 亚洲一卡久久| 欧美在线观看一区二区三区| 国产欧美日韩三区| 久久大逼视频| 欧美va亚洲va香蕉在线| 亚洲第一在线视频| 欧美精品色综合| 一区二区国产日产| 亚洲欧美文学| 激情视频一区二区三区| 久久―日本道色综合久久| 欧美a级大片| 亚洲精选在线观看| 欧美视频一区二区三区| 亚洲一区综合| 亚洲欧美另类在线| 狠狠色综合网站久久久久久久| 久久伊人精品天天| 亚洲青涩在线| 久久精品成人一区二区三区| 国产字幕视频一区二区| 免费在线观看成人av| 99精品国产在热久久下载| 欧美一区二区三区男人的天堂 | 亚洲一级在线观看| 免费欧美日韩| 亚洲一区在线播放| 一区二区在线观看视频在线观看| 噜噜爱69成人精品| 日韩亚洲国产欧美| 久久亚洲视频| 亚洲午夜精品17c| 国内精品久久久久久 | 99精品国产热久久91蜜凸| 久久精品国产一区二区三| 亚洲人成人一区二区三区| 国产精品视频在线观看| 女人色偷偷aa久久天堂| 亚洲欧美高清| 亚洲裸体俱乐部裸体舞表演av| 欧美呦呦网站| 亚洲午夜视频| 亚洲黄色高清| 国产一区免费视频| 欧美视频一区二区三区| 久热精品视频在线观看| 亚洲欧美国产一区二区三区| 最新日韩av| 久久亚洲一区二区三区四区| 亚洲综合精品| 99视频一区二区| 尤物精品在线| 国产一区在线视频| 国产毛片久久| 欧美日韩在线播放一区二区| 老鸭窝91久久精品色噜噜导演| 性久久久久久久久| 亚洲理伦在线| 免费在线视频一区| 久久久亚洲欧洲日产国码αv | 亚洲无线观看| 一本久道久久综合中文字幕| 亚洲国产毛片完整版| 免费欧美在线| 欧美va亚洲va香蕉在线| 老司机精品视频一区二区三区| 久久大逼视频| 欧美在线视屏| 久久不见久久见免费视频1| 亚洲片在线观看| 亚洲人成在线观看| 亚洲激情另类| 亚洲美女黄色片| 夜夜嗨av一区二区三区中文字幕| 亚洲精品欧美激情| aⅴ色国产欧美| 一区二区三区免费看| 一本色道久久精品| 亚洲一区二区免费视频| 亚洲视频在线观看三级| 亚洲视频国产视频| 亚洲一区二区久久| 欧美一级在线播放| 久久久久国产一区二区三区| 久久成人资源| 美女爽到呻吟久久久久| 免费国产一区二区| 最新国产精品拍自在线播放| 日韩一级大片| 亚洲永久精品国产| 久久久久欧美精品| 欧美国产三区| 国产精品毛片在线看| 国产视频精品网| 最新日韩av| 99在线热播精品免费| 亚洲一区二区三区午夜| 欧美一区二区在线看| 六十路精品视频| 日韩视频在线免费| 午夜欧美精品| 欧美sm视频| 国产精品一区视频| 亚洲国产精品福利| 亚洲一区二区三区在线观看视频| 欧美一区二区三区视频| 免费日韩成人| 一区二区日本视频| 久久xxxx| 久久综合精品一区| 国产精品热久久久久夜色精品三区| 黄色日韩网站| 亚洲午夜久久久久久久久电影网| 久久综合九色九九|