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

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>
            久久五月天婷婷| 国语自产精品视频在线看8查询8 | 亚洲高清在线观看| 久久av一区二区三区漫画| 国产一区二区三区电影在线观看| 久久精品免费| 亚洲欧美日韩综合一区| 国产一区二区三区四区在线观看 | 欧美日韩国产成人在线| 一本色道精品久久一区二区三区| 亚洲日韩视频| 国产精品日韩在线观看| 久久亚洲欧美国产精品乐播| 免费看av成人| 亚洲一二三级电影| 久久精品动漫| 一本色道久久加勒比精品| 亚洲一区二区三区国产| 精品99一区二区| 亚洲免费电影在线| 国内精品模特av私拍在线观看| 欧美国产日韩一二三区| 国产精品久久二区| 欧美成人精品一区二区三区| 国产精品久久77777| 欧美99久久| 国产精品入口麻豆原神| 亚洲高清在线播放| 国产日韩欧美日韩| 亚洲精品你懂的| 国产精品一区二区在线观看网站| 欧美成人免费全部| 国产女人精品视频| 亚洲精品一区二区三区av| 精品999日本| 亚洲尤物在线| 日韩小视频在线观看专区| 久久久国产亚洲精品| 亚洲免费一在线| 欧美精品国产一区| 欧美1区3d| 国产一区二区| 亚洲欧美日本视频在线观看| 99国产精品国产精品毛片| 老司机67194精品线观看| 久久国产精品99国产| 国产精品啊啊啊| 亚洲精品免费在线播放| 亚洲精品久久久久| 久久日韩粉嫩一区二区三区| 久久久久综合网| 国产亚洲欧美色| 亚洲欧美国产毛片在线| 亚洲一区二区三区精品视频| 欧美日韩福利在线观看| 亚洲精华国产欧美| 日韩一级视频免费观看在线| 另类专区欧美制服同性| 免费亚洲电影| 亚洲国产日韩在线一区模特| 久久精品一区二区国产| 久久久噜噜噜久久中文字免| 国产日韩欧美视频| 亚洲欧美伊人| 久久久久成人精品| 国产真实久久| 久久久天天操| 亚洲第一色在线| 日韩小视频在线观看专区| 欧美精品久久久久久久久久| 亚洲美女黄色片| 亚洲一区中文| 国产日韩欧美一区| 久久精品亚洲一区| 欧美激情第一页xxx| 亚洲青涩在线| 欧美精品日韩精品| 亚洲另类在线一区| 小处雏高清一区二区三区| 国产午夜久久久久| 久久婷婷色综合| 亚洲精品免费一区二区三区| 亚洲一区二区视频在线| 国产欧美日韩| 久久综合网色—综合色88| 91久久黄色| 午夜视频一区| 亚洲东热激情| 欧美日韩在线不卡一区| 午夜精品视频在线观看| 欧美二区在线播放| 亚洲一区二区三区免费观看| 国产情侣久久| 欧美经典一区二区| 亚洲欧美日韩国产综合精品二区| 久久午夜电影| 亚洲视频二区| 狠狠干成人综合网| 欧美日韩国产va另类| 午夜影院日韩| 亚洲精品视频在线看| 久久精品国产清高在天天线| 亚洲精品视频啊美女在线直播| 国产精品人人爽人人做我的可爱| 久久久精品五月天| 亚洲视频播放| 欧美国产在线观看| 久久高清一区| 亚洲视频中文字幕| 亚洲国产精品一区二区尤物区| 国产精品a久久久久| 久久人人爽人人爽爽久久| 一区二区三区四区五区精品| 久久在线免费观看视频| 亚洲女人av| av不卡在线| 亚洲国产日韩欧美综合久久 | 久久人人爽人人| 亚洲自拍偷拍视频| 日韩视频国产视频| 欧美护士18xxxxhd| 久久午夜影视| 欧美一区二区日韩| 亚洲综合色网站| 一区二区成人精品| 亚洲精品中文字幕有码专区| 国产自产v一区二区三区c| 国产精品老女人精品视频| 欧美日韩亚洲另类| 欧美韩日一区| 免费在线看一区| 美女图片一区二区| 久久影院午夜论| 久久视频国产精品免费视频在线| 欧美主播一区二区三区美女 久久精品人 | 亚洲视频www| 99视频精品| 9色porny自拍视频一区二区| 亚洲激情在线视频| 亚洲国产经典视频| ●精品国产综合乱码久久久久| 国产自产女人91一区在线观看| 国产亚洲成精品久久| 国产亚洲制服色| 狠狠色狠狠色综合| 国产一区亚洲一区| 国产专区综合网| 一区二区亚洲精品| 亚洲大片一区二区三区| 亚洲国产小视频在线观看| 亚洲国产精品999| 亚洲精品视频中文字幕| 99国产精品99久久久久久| 亚洲视频你懂的| 欧美一级午夜免费电影| 久久精品视频网| 欧美1区免费| 亚洲日本激情| 亚洲男人的天堂在线aⅴ视频| 亚洲欧美自拍偷拍| 老司机免费视频一区二区三区| 免费日韩av片| 欧美视频一二三区| 国产一区二区精品在线观看| 在线观看欧美精品| 99精品视频免费全部在线| 午夜精品免费| 看欧美日韩国产| 亚洲欧洲一区二区在线播放| 亚洲一区二区三区久久| 久久青草欧美一区二区三区| 欧美精品日韩| 国产一区二区三区成人欧美日韩在线观看 | 国产区在线观看成人精品| 玉米视频成人免费看| 一区二区三区四区五区在线 | 在线精品亚洲| 一区二区三区四区蜜桃| 久久久久国产一区二区三区四区| 欧美成人精品激情在线观看| 99视频超级精品| 久久久久久高潮国产精品视| 欧美日韩国产色视频| 精品av久久久久电影| 亚洲专区一区二区三区| 能在线观看的日韩av| 亚洲在线观看| 欧美激情一区二区三区全黄| 国产一区二区无遮挡| 一区二区三区视频在线看 | 99riav国产精品| 亚洲图片在线| 亚洲最快最全在线视频| 久久精品1区| 国产精品入口福利| 亚洲免费大片| 欧美韩日高清| 久久久99久久精品女同性| 国产精品日韩欧美一区| 99在线精品免费视频九九视|