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

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>
            国产日韩在线一区二区三区| 国产精品swag| 亚洲精品一区二区三区av| 欧美激情第一页xxx| 欧美激情第3页| 亚洲小视频在线观看| 亚洲午夜免费视频| 国产一区二区三区观看| 欧美顶级艳妇交换群宴| 欧美精品综合| 欧美在线二区| 欧美成人自拍| 性欧美大战久久久久久久免费观看| 午夜免费电影一区在线观看| 亚洲高清资源| 中文日韩电影网站| 伊人久久婷婷色综合98网| 亚洲黄色高清| 国产精品日韩在线| 欧美激情91| 国产精品女主播| 亚洲国产精品ⅴa在线观看| 国产精品国产a| 欧美aa在线视频| 欧美色播在线播放| 欧美a级大片| 国产精品视频免费观看| 欧美国产日本在线| 国产午夜精品久久久久久久| 欧美黄色影院| 国内精品久久久久影院优 | 精品99视频| 一本色道久久综合亚洲二区三区 | 欧美人与禽猛交乱配| 久久视频在线视频| 欧美视频一区二区三区在线观看 | 亚洲精品裸体| 亚洲国产天堂久久综合网| 亚洲主播在线播放| 在线一区二区三区四区| 久久综合久久综合九色| 久久精品夜色噜噜亚洲a∨| 欧美久久精品午夜青青大伊人| 久久久久免费| 国产日韩亚洲欧美精品| 一本久久a久久精品亚洲| 亚洲精品免费电影| 久久手机免费观看| 久久综合一区二区三区| 国产亚洲一区在线| 先锋影音国产精品| 欧美一区二区视频在线| 国产精品国产馆在线真实露脸| 欧美激情一区在线观看| 激情综合色综合久久| 亚洲尤物影院| 久久精品国产精品 | 欧美美女日韩| 欧美国产日本在线| 亚洲国产精品成人| 美女脱光内衣内裤视频久久影院| 久久夜色精品国产欧美乱| 国产一区视频在线看| 午夜在线电影亚洲一区| 久久精品一区二区| 黄色成人片子| 蜜桃伊人久久| 亚洲高清自拍| 99综合视频| 国产精品毛片在线| 小黄鸭精品密入口导航| 久久久久久穴| 狠狠色香婷婷久久亚洲精品| 久久精品视频在线看| 免费久久精品视频| 日韩视频在线免费| 欧美性猛交99久久久久99按摩| 一本一本久久a久久精品综合妖精| 亚洲午夜久久久| 国产欧美一区视频| 另类亚洲自拍| 日韩一级大片在线| 久久精品免费播放| 亚洲国产欧美一区二区三区同亚洲| 欧美va亚洲va国产综合| 日韩视频免费观看高清在线视频| 亚洲手机成人高清视频| 国产精品日韩精品欧美精品| 久久国产一区| 亚洲精品国产精品乱码不99按摩| 亚洲欧美日韩国产一区二区三区| 国产有码在线一区二区视频| 蜜桃av综合| 亚洲尤物精选| 欧美激情亚洲激情| 欧美一级大片在线免费观看| 在线精品视频在线观看高清| 欧美色视频一区| 久久精品综合| 亚洲视频播放| 欧美激情一级片一区二区| 亚洲欧美日韩在线高清直播| 亚洲国产精品悠悠久久琪琪| 欧美性淫爽ww久久久久无| 久久久久久综合网天天| 一区二区日韩| 亚洲成人在线视频网站| 欧美一区二区女人| 9色国产精品| 亚洲大胆视频| 国产一区二区久久| 欧美日韩综合在线| 欧美aⅴ一区二区三区视频| 午夜免费在线观看精品视频| 亚洲精品资源美女情侣酒店| 蜜桃av噜噜一区| 久久高清国产| 亚洲综合第一页| 亚洲九九九在线观看| 激情久久久久久久| 国产欧美欧美| 国产精品国产三级国产专区53| 欧美电影美腿模特1979在线看| 久久精彩视频| 亚洲欧美日韩综合| 亚洲影院色无极综合| 日韩午夜在线观看视频| 亚洲国产日韩欧美| 欧美国产日韩一区二区三区| 乱中年女人伦av一区二区| 性色av一区二区三区| 亚洲欧美日韩天堂一区二区| 在线亚洲欧美视频| 99这里只有久久精品视频| 亚洲另类视频| 亚洲精品中文字幕在线观看| 亚洲国产精品一区制服丝袜| 在线播放一区| 亚洲国产成人在线播放| 亚洲国产精品女人久久久| 在线成人免费视频| 亚洲第一精品夜夜躁人人躁| 一区二区三区在线不卡| 激情五月婷婷综合| 在线精品视频在线观看高清| 亚洲国产国产亚洲一二三| 亚洲人成艺术| 9色精品在线| 亚洲欧美国产日韩中文字幕| 午夜久久资源| 久久国产精品高清| 蜜臀av性久久久久蜜臀aⅴ| 久久精品国产精品| 麻豆精品视频在线观看| 欧美激情亚洲| 中文欧美日韩| 欧美一区二区播放| 免费观看亚洲视频大全| 欧美片在线观看| 国产精品久久久久aaaa| 国产视频久久| 1024精品一区二区三区| 亚洲日本中文| 午夜一区在线| 欧美+亚洲+精品+三区| 最新国产乱人伦偷精品免费网站 | 亚洲精选中文字幕| 亚洲欧美国产日韩天堂区| 久久久久免费| 欧美深夜影院| 激情欧美国产欧美| 一区二区三区欧美亚洲| 久久精品国产v日韩v亚洲| 欧美国产综合| 亚洲综合三区| 欧美成人午夜| 国产欧美一区二区三区沐欲 | 亚洲一区二区三区精品动漫| 久久国产精品色婷婷| 91久久精品国产91性色| 亚洲欧美中文另类| 欧美欧美全黄| 黄色国产精品| 亚洲欧美日韩国产一区二区| 免费观看在线综合色| 亚洲私人黄色宅男| 亚洲激情另类| 欧美伊人影院| 亚洲黄网站在线观看| 性欧美videos另类喷潮| 欧美久久久久久久久| 在线不卡欧美| 欧美一区二区啪啪| 一本色道久久精品| 免费欧美在线| 在线观看三级视频欧美| 亚洲欧美三级伦理| 日韩一区二区精品在线观看| 久久午夜精品一区二区| 国产日韩欧美在线一区|