]]>
]]>
]]>
鍘熸枃鍦板潃錛?a title="http://www.shnenglu.com/xiaoyisnail/archive/2009/09/21/96883.html" href="http://www.shnenglu.com/xiaoyisnail/archive/2009/09/21/96883.html">http://www.shnenglu.com/xiaoyisnail/archive/2009/09/21/96883.html
鏈枃鐗堟潈褰掍綔鑰呭拰cppblog鍏辨湁錛屾榪庤漿杞斤紝浣嗘湭緇忎綔鑰呭悓鎰忓繀欏諱繚鐣欐孌靛０鏄庯紝涓斿湪鏂囩珷欏甸潰鏄庢樉浣嶇疆緇欏嚭鍘熸枃榪炴帴錛屽惁鍒欎繚鐣欒拷絀舵硶寰嬭矗浠葷殑鏉冨埄銆?
緇堜簬鏈夋椂闂村啓鏈枃鐨勭浜岄儴鍒嗕簡銆傚湪涓婁竴綃?/font>鏂囩珷(涓嬫枃涓О涓?#8220;鏂?涓)”)涓紝鎴戞彁鍑轟簡涓涓叿浣撶殑闂“鍙兘鐢?,-鍜屼綅榪愮畻瀹炵幇姝?/span>鏁存暟闄ゆ硶(/)鍜屽彇妯?%)”錛屽茍鏁寸悊浜嗕竴浜涘拰浣嶈繍綆楃浉鍏崇殑棰樼洰鍜岀畻娉曪紝鏈枃灝嗙粰鍑轟笂榪伴棶棰樼殑涓涓畬鏁寸殑瑙ｇ瓟鎬濊礬鍜屽疄鐜般?/font>
棣栧厛鎬濊冩渶綆鍗曠殑闄ゆ硶瀹炵幇錛屽嵆寰幆鍑忛櫎鏁幫紝鍑忓埌涓嶈兘鍐嶅噺涓烘錛屾墍鍑忔鏁板嵆鎵姹傜殑鍟嗭紝浜嬪疄涓婅繖灝辨槸鎴戜滑鍒濆鍥涘垯榪愮畻鏃跺闄ゆ硶鐨勫畾涔夛紝瀹炵幇錛?/font>
1
int integer_div_0(int dividend, int divisor)
2
{
3
if(divisor == 0)
4
{
5 cout<<"闈炴硶鍙傛暟錛岄櫎闆墮敊"<<endl;
6 exit(1);
7
}
8
9 int res = 0;
10 while((dividend-=divisor)>=0)
11 ++res;
12
13 return res;
14
}
int integer_div_0(int dividend, int divisor)2
{
3
if(divisor == 0)4
{
5
cout<<"闈炴硶鍙傛暟錛岄櫎闆墮敊"<<endl;6
exit(1);7
}8
9
int res = 0;10
while((dividend-=divisor)>=0)11
++res;12
13
return res;14
}寰堟樉鐒訛紝榪欎釜綆鍗曠殑瀹炵幇鏄潪甯鎬綆鏁堢殑錛屾眰integer_div_0(a,b)鐨勬椂闂村鏉傚害涓篛(a/b)錛屽綋a寰堝ぇb寰堝皬鏃訛紝璁＄畻寮閿寰堝ぇ錛屾湁浠涔堝姙娉曡兘鎻愰珮鏁堢巼鍚楋紵鑰冭檻鍒板驚鐜噺闄ゆ暟鍚屾椂姣旇緝宸槸鍚﹀ぇ浜庣瓑浜?鏈夌偣綾諱技浜庡湪涓涓竴涓暟緇勬垨鏄痩inked list涓『搴忔悳绱㈡煇涓洰鏍囧鹼紝鍦ㄨ緝宸殑鎯呭喌涓嬭繎浼間簬鎼滅儲鏁翠釜闂絀洪棿錛岃繖鏍風殑寮閿蹇呯劧寰堝ぇ錛岄偅涔堝彧瑕佹壘鍒版煇涓柟娉曟潵鍑忓皯闇瑕佹悳绱㈢殑闂絀洪棿灝卞彲浠ユ彁楂樻ц兘浜嗐備簬鏄紝鑷劧鍙互鎯沖埌濡備笅綆楁硶錛氫互闄ゆ暟涓哄垵濮嬫祴璇曞鹼紝浠?鐨勬寚鏁頒負姝ラ暱鏉ユ悳绱㈤棶棰樼┖闂達紝褰撹闄ゆ暟涓庢祴璇曞肩殑宸皬浜庨櫎鏁版椂渚跨粨鏉熸悳绱紝鑻ュ湪榪欎箣鍓嶆祴璇曞煎ぇ浜庤闄ゆ暟錛屽垯灝嗚闄ゆ暟鍑忓幓鍓嶄竴涓祴璇曞鹼紝騫墮噸澶嶄笂榪拌繃紼嬬洿鍒版悳绱㈢粨鏉熴備婦涓緥瀛愶紝姹?200/3錛?br>欏哄簭鎼滅儲鏃訛紝鎴戜滑瑕佷笌1200姣旇緝鐨勬暟鏈夛細3,6,9,12,15,...,1998,2001錛屾瘮杈冩鏁?67嬈?br>浠?鐨勬寚鏁頒負姝ラ暱鎼滅儲鏃訛紝涓?200姣旇緝3,6,12,24,48,96,192,384,768,1536錛岀劧鍚庝笌1200-768=432鍐嶈繘琛屾瘮杈?,6,12,24,48,96,192,384,768錛屽啀鍙?32-384=48姣旇緝3,6,12,24,48錛屾悳绱㈢粨鏉燂紝姣旇緝嬈℃暟鍏?4嬈★紝姣旈『搴忔悳绱㈡湁寰堝ぇ鐨勬彁楂樸備綘鍙兘浼氶棶錛屼負浠涔堣浠?鐨勬寚鏁頒負姝ラ暱鏉ユ悳绱㈠憿錛熺瓟妗堟槸錛岃繖鏍鋒垜浠氨鍙互浣跨敤浣嶆搷浣滄潵榪涗竴姝ユ彁楂樿綆楁晥鐜囦簡銆備笅闈㈡槸榪欎釜綆楁硶鐨勫疄鐜幫細
1int integer_div_1(unsigned int dividend, unsigned int divisor)
2{
3 if(divisor == 0)
4 {
5 cout<<"闈炴硶鍙傛暟錛岄櫎闆墮敊"<<endl;
6 exit(1);
7 }
8
9 if(dividend < divisor) return 0;
10 unsigned int k=0,c=divisor, res=0;
11
12 for(;dividend>=c;c<<=1,k++)
13 if(dividend-c < divisor)
14 return 1<<k;
15
16 return integer_div_1(dividend-(c>>1), divisor)+(1<<(k-1));
17}
娉ㄦ剰鍒版渶鍚庝竴琛岀殑灝鵑掑綊錛屽啀鎶婁唬鐮佷紭鍖栦負闈為掑綊濡備笅錛?br>
int integer_div_1(unsigned int dividend, unsigned int divisor)2
{3
if(divisor == 0)4
{5
cout<<"闈炴硶鍙傛暟錛岄櫎闆墮敊"<<endl;6
exit(1);7
}8
9
if(dividend < divisor) return 0;10
unsigned int k=0,c=divisor, res=0;11
12
for(;dividend>=c;c<<=1,k++)13
if(dividend-c < divisor)14
return 1<<k;15
16
return integer_div_1(dividend-(c>>1), divisor)+(1<<(k-1));17
} 1//闈為掑綊鏁存暟闄ゆ硶
2int integer_div_2(unsigned int dividend, unsigned int divisor)
3{
4 if(divisor == 0)
5 {
6 cout<<"闈炴硶鍙傛暟錛岄櫎闆墮敊"<<endl;
7 exit(1);
8 }
9
10 if(dividend < divisor) return 0;
11 unsigned int k, c, res=0;
12
13 while(dividend > divisor)
14 {
15 for(k=0,c=divisor;dividend>=c;c<<=1,k++)
16 {
17 if(dividend-c < divisor)
18 {
19 res += 1<<k;
20 break;
21 }
22 }
23 if(dividend-c < divisor)
24 break;
25
26 res += 1<<(k-1);
27 dividend -= c>>1;
28 }
29
30 return res;
31}
鏈鍚庯紝鏈変簡鏁存暟闄ゆ硶錛屽彇妯¤繍綆楀氨寰堢畝鍗曚簡錛屼粠榪涜鏁存暟闄ゆ硶鎼滅儲鍟嗙殑鏈鍚庝竴姝ョ珛鍒誨氨鑳藉緱鍒版ā闄ょ殑浣欐暟錛屽疄鐜板涓嬶紝涓轟簡鏂逛究璧瘋錛屼唬鐮侀噷浣跨敤C++ STL涓殑pair妯℃澘浠ュ悓鏃惰繑鍥炲晢鍜屼綑鏁幫細//闈為掑綊鏁存暟闄ゆ硶2
int integer_div_2(unsigned int dividend, unsigned int divisor)3
{4
if(divisor == 0)5
{6
cout<<"闈炴硶鍙傛暟錛岄櫎闆墮敊"<<endl;7
exit(1);8
}9
10
if(dividend < divisor) return 0;11
unsigned int k, c, res=0;12
13
while(dividend > divisor)14
{15
for(k=0,c=divisor;dividend>=c;c<<=1,k++)16
{17
if(dividend-c < divisor)18
{19
res += 1<<k;20
break;21
} 22
}23
if(dividend-c < divisor)24
break;25
26
res += 1<<(k-1);27
dividend -= c>>1;28
}29
30
return res;31
} 1//鏁存暟闄ゆ硶and鍙栨ā錛岃繑鍥炲晢鍜屼綑鏁?/span>
2pair<int,int> integer_div_3(unsigned int dividend, unsigned int divisor)
3{
4 if(divisor == 0)
5 {
6 cout<<"闈炴硶鍙傛暟錛岄櫎闆墮敊"<<endl;
7 exit(1);
8 }
9
10 if(dividend < divisor)
11 return make_pair(0, dividend);
12 unsigned int k, c, quotient=0, remainder;
13
14 while(dividend > divisor)
15 {
16 for(k=0,c=divisor;dividend>=c;c<<=1,k++)
17 {
18 if(dividend-c < divisor)
19 {
20 quotient += 1<<k;
21 remainder = dividend-c;
22 break;
23 }
24 }
25 if(dividend-c < divisor)
26 break;
27
28 quotient += 1<<(k-1);
29 dividend -= c>>1;
30 }
31
32 return make_pair(quotient, remainder);
33}
//鏁存暟闄ゆ硶and鍙栨ā錛岃繑鍥炲晢鍜屼綑鏁?/span>2
pair<int,int> integer_div_3(unsigned int dividend, unsigned int divisor)3
{4
if(divisor == 0)5
{6
cout<<"闈炴硶鍙傛暟錛岄櫎闆墮敊"<<endl;7
exit(1);8
}9
10
if(dividend < divisor) 11
return make_pair(0, dividend);12
unsigned int k, c, quotient=0, remainder;13
14
while(dividend > divisor)15
{16
for(k=0,c=divisor;dividend>=c;c<<=1,k++)17
{18
if(dividend-c < divisor)19
{20
quotient += 1<<k;21
remainder = dividend-c;22
break;23
} 24
}25
if(dividend-c < divisor)26
break;27
28
quotient += 1<<(k-1);29
dividend -= c>>1;30
}31
32
return make_pair(quotient, remainder);33
}鍐欏埌榪欓噷錛岀畻鏄妸鍏ㄦ枃鐨勪換鍔￠兘瀹屾垚浜嗭紝璇昏呭彲鑳借寰楁枃(涓)鍜屾枃(浜?閲岃鍒扮殑涓浜涢鐩殑鍏崇郴涓嶅ぇ錛屼絾鎴戝啓榪欎袱綃囨枃绔犵殑鐩殑灝辨槸鎯沖己璋?span style="color: red;">浣嶈繍綆楃殑浣滅敤
錛屾垨鑰呰浜岃繘鍒剁殑緹?/span>錛屽緢澶氭椂鍊欏鏋滄垜浠崲涓搴︼紝鐢ㄤ簩榪涘埗鏉ユ濊冮棶棰橈紝涔熻浼氱獊鐒?#8220;Aha!Insight!”錛屼粠鑰屽緱鍒頒竴涓紭緹庣殑瑙ｇ瓟銆?/p>]]>
]]>
F(n,k)=min{max{F(r,k-1), F(n-r,k)}+1, 1<=r<=n}
杈圭晫鏉′歡:F(n,1)=n-1, F(1,k)=F(0,k)=0
鐘舵佽漿縐繪柟紼嬪彲浠ヨ繖鏍鋒潵鑰冭檻錛屽亣璁懼湪n灞傛ゼ涓殑絎瑀灞傛姏涓嬈?瀵瑰簲鏂圭▼涓殑"+1")錛屼細鏈変袱縐嶆儏鍐靛彂鐢燂細
(1)鐜葷拑鐞冪錛岃鏄庡湪絎?鍒扮r灞傛ゼ涓繀鏈変竴灞備負涓寸晫灞傦紝闂杞寲涓轟竴涓瓙闂錛氭眰F(r,k-1)
(2)鐜葷拑鐞冧笉紕庯紝璇存槑涓寸晫灞傚湪絎瑀+1灞傚埌絎琻灞傝繖n-r灞傛ゼ涓紝闂杞寲涓哄瓙闂:姹侳(n-r,k)
鍥犱負鑰冭檻鐨勬槸鏈鍧忔儏鍐典笅鎶涚悆絳栫暐鐨勬墍闇嫻嬭瘯嬈℃暟鐨勬渶灝忓鹼紝鎵浠ュ彇榪欎袱縐嶆儏鍐典腑鐨勮緝澶у鹼紝騫墮亶鍘嗘瘡涓涓彲鑳界殑r錛屽彇鍏舵渶灝忓煎嵆寰楀埌F(n,k)銆?br> 瀹炵幇浠ｇ爜濡備笅錛?br>
1 #include <iostream>
2 #include <fstream>
3 #include <sstream>
4 #include <string>
5 #include <cmath>
6 #include <iomanip>
7 #include <vector>
8 #include <deque>
9 #include <list>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <algorithm>
14 #include <limits>
15 #include <utility>
16 #include <ctime>
17 #include <bitset>
18 using namespace std;
19
20 #define MAX_FLOOR 512
21 #define MAX_BALL 100
22
23 int dp(int n, int k)
24 {
25 if(k<1 || n<1) return -1; //閿欒杈撳叆
26
27 if(k==1) return n-1; //鍘繪帀涓浜泃rivial case
28 if(n==1) return 0;
29
30 int M[MAX_BALL][MAX_FLOOR];
31 int i,j,r;
32 int temp, min;
33
34 for(i=0;i<=k;i++) M[i][0]=M[i][1]=0; //F(1,k)=F(0,k)=0
35 for(j=2;j<=n;j++) M[1][j]=j-1; //F(n,1)=n-1
36
37 /*
38 鐘舵佽漿縐繪柟紼嬶細
39 F(n,k)=min{max{F(r,k-1)+1, F(n-r,k)+1}, 1<=r<=n}
40 */
41 for(i=2;i<=k;i++)
42 for(j=2;j<=n;j++)
43 {
44 min = numeric_limits<int>::max();
45 for(r=1;r<=j;r++)
46 {
47 temp = max(M[i-1][r], M[i][j-r])+1;
48 if(temp<min)
49 min = temp;
50 }
51 M[i][j] = min;
52 }
53
54 return M[k][n];//F(n,k)
55 }
56
57 int main()
58 {
59 int n,k;
60
61 cin>>n>>k;
62 cout<<dp(n, k)<<endl;
63
64 return 0;
65 }
2 #include <fstream>
3 #include <sstream>
4 #include <string>
5 #include <cmath>
6 #include <iomanip>
7 #include <vector>
8 #include <deque>
9 #include <list>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <algorithm>
14 #include <limits>
15 #include <utility>
16 #include <ctime>
17 #include <bitset>
18 using namespace std;
19
20 #define MAX_FLOOR 512
21 #define MAX_BALL 100
22
23 int dp(int n, int k)
24 {
25 if(k<1 || n<1) return -1; //閿欒杈撳叆
26
27 if(k==1) return n-1; //鍘繪帀涓浜泃rivial case
28 if(n==1) return 0;
29
30 int M[MAX_BALL][MAX_FLOOR];
31 int i,j,r;
32 int temp, min;
33
34 for(i=0;i<=k;i++) M[i][0]=M[i][1]=0; //F(1,k)=F(0,k)=0
35 for(j=2;j<=n;j++) M[1][j]=j-1; //F(n,1)=n-1
36
37 /*
38 鐘舵佽漿縐繪柟紼嬶細
39 F(n,k)=min{max{F(r,k-1)+1, F(n-r,k)+1}, 1<=r<=n}
40 */
41 for(i=2;i<=k;i++)
42 for(j=2;j<=n;j++)
43 {
44 min = numeric_limits<int>::max();
45 for(r=1;r<=j;r++)
46 {
47 temp = max(M[i-1][r], M[i][j-r])+1;
48 if(temp<min)
49 min = temp;
50 }
51 M[i][j] = min;
52 }
53
54 return M[k][n];//F(n,k)
55 }
56
57 int main()
58 {
59 int n,k;
60
61 cin>>n>>k;
62 cout<<dp(n, k)<<endl;
63
64 return 0;
65 }
input: 100 2 output: 14
input: 300 3 output: 13
]]>
涓轟簡涓嶈瀵煎ぇ瀹訛紝鎶婇鐩敼浜嗭紝鑷充簬涓嬮潰鐨勭瑪璇曢錛屽笇鏈涚墰浜虹粰浜堣В絳斿晩錛岃阿璋€?/span>
---------------------------------------鍘熸枃鍒嗗壊綰?----------------------------------------------
蹇鎵懼伐浣滀簡錛岀幇鍦ㄥ湪鍥為【涓浜涚畻娉曞拰鏁版嵁緇撴瀯鐨勭煡璇嗭紝闄や簡鐪嬩功錛屼簤鍙栨瘡澶╂寫涓涓ら亾鏈夎叮鐨勯鐩潵緇冪粌鎵嬨傛湰浜烘病鍙傚姞榪嘇CM錛岃В綆楁硶棰樼殑瀹炲姏涔熺浉褰撹彍楦燂紝浣嗘湰浜哄浜庝換浣曡兘澶熼敾鐐兼濈淮鑳藉姏鐨勯鐩兘鐩稿綋鐑》錛屼笉鎬曞仛涓嶅嚭鏉ワ紝灝辨曚笉鏁㈠仛錛屽仛澶氫簡錛屾濊冨浜嗭紝鎬繪槸鏈夊府鍔╃殑錛屽懙鍛碉紝鎵浠ュ笇鏈涘悇浣嶇湅鍒版垜鐨勬枃绔犱腑鏈夐敊璇殑鍦版柟璇蜂笉鍚濊祼鏁欙紝鍦ㄤ笅鎰熸縺涓嶅敖銆?br>Share is happiness.
浠婂ぉ鐨勯鐩槸鍦ㄧ綉涓婄湅鍒扮殑錛宮s鏄竴閬揵aidu鐨勭瑪璇曢錛?br> 緇欏畾涓涓簭鍒梐[0...n-1]鍜屼竴鏁存暟m錛屾弧瓚?<=m<=n-1錛屼笖a[0...m-1]鍜宎[m...n-1]閮戒負鏈夊簭瀛愬簭鍒楋紝瑕佹眰璁捐涓涓椂闂村鏉傚害涓篛(N)錛岀┖闂村鏉傚害涓篛(1)鐨勭畻娉曪紝瀹炵幇灝嗚繖涓や釜瀛愬簭鍒楀悎騫朵負涓涓畬鏁寸殑鏈夊簭搴忓垪a[0...n-1]銆?br>
棰樻剰寰堢畝鍗曪紝灝辨槸瑕佽璁′竴涓嚎鎬ф椂闂寸殑鍘熷湴褰掑茍綆楁硶錛屾垜緇欏嚭鐨勬濊礬錛?br> 浠庡乏鍒板彸閬嶅巻鏁扮粍錛屽皢褰撳墠鏈亶鍘嗗厓绱犱腑鐨勬渶灝忓肩疆鎹㈠埌瀹冩墍搴斿湪鐨勪綅緗傝繖涓畝鍗曠殑鎻忚堪鏈夌偣鍍忛夋嫨鎺掑簭錛屼絾閫夋嫨鎺掑簭O(N^2)鐨勫鏉傚害鏄庢樉鏄笉鍏佽鐨勶紝榪欓噷錛屽埄鐢ㄤ袱涓瓙搴忓垪宸叉湁搴忕殑鎬ц川錛屾垜浠彲浠ヨ璁℃洿楂樻晥鐨凮(N)綆楁硶錛氶鍏堟槗鐭ユ湭閬嶅巻鍏冪礌涓殑鏈灝忓煎繀瀹氭槸涓や釜瀛愬簭鍒楃殑鏈灝忓間腑鐨勬洿灝忚咃紝灝嗘敼鍊間氦鎹㈠埌瀹冨簲鍦ㄧ殑浣嶇疆錛涘埄鐢ㄦ湁搴忔э紝鍙互鍦ㄩ亶鍘嗚繃紼嬩腑鍒嗗埆璁板綍涓や釜瀛愬簭鍒楃殑褰撳墠鏈灝忓厓绱犵殑浣嶇疆錛岃繖鏍峰氨鐪佸幓浜嗛夋嫨鎺掑簭涓瘡嬈￠兘瑕侀亶鍘嗗墿浣欏簭鍒楁壘鍑烘渶灝忓肩殑寮閿錛屾瘡嬈￠亶鍘嗗唴閮ㄤ負甯告暟嬈＄殑姣旇緝鍜屼氦鎹㈡搷浣滐紝鎵浠ユ暣涓畻娉曠殑鏃墮棿澶嶆潅搴︿負O(N)銆?br>
]]>