寤鴻鍏堢湅鐪嬪墠璦錛?a style="color: rgb(49,52,40); text-decoration: none" >http://www.wutianqi.com/?p=2298
榪炶澆鎬葷洰褰曪細(xì)http://www.wutianqi.com/?p=2403
璇村埌璐績(jī)綆楁硶錛岄伩鍏嶄笉浜?jiǎn)浜嶥P瀵規(guī)瘮錛屾墍浠ュ墠闈㈢殑DP瑕佷簡(jiǎn)瑙ｃ?/p>
璐績(jī)綆楁硶鏄嬌鎵鍋氱殑閫夋嫨鐪嬭搗鏉ラ兘鏄綋鍓嶆渶浣崇殑錛屾湡鏈涢氳繃鎵鍋氱殑灞閮ㄦ渶浼橀夋嫨鏉ヤ駭鐢熶竴涓叏灞鏈浼樿В銆?/span>
渚濈劧鍜屼笂涓绔犳葷粨DP涓鏍鳳紝鎴戝厛緇欏嚭涓涓渶瀹規(guī)槗鍏ラ棬鐨勪緥瀛愶紝鏉ョ湅鐪嬬椹槸璐績(jī)錛?鏄漢灝變細(xì)璐績(jī)錛岃繖涓畻娉曞緢浜烘у寲鍟?/p>
=銆?)
涓涓渶綆鍗曠殑渚嬪瓙錛?/p>
閮ㄥ垎鑳屽寘闂錛?/p>
鏈塏涓墿鍝侊紝絎琲涓墿鍝佷環(huán)鍊紇i錛岄噸wi錛岀幇鍦ㄤ綘鏈変竴涓彲浠ヨW 紓呯殑鍖咃紝浣犲彲浠ラ夋嫨甯﹁蛋姣忎釜鐗╁搧鐨勫叏閮ㄦ垨涓閮ㄥ垎錛屾眰濡備綍閫夋嫨鍙互浣胯儗鍖呮墍瑁呯殑浠峰兼渶澶э紵(榪欎釜鏄笉鏄拰鍓嶉潰DP涓鐨?1鑳屽寘寰堝儚錛熻鐪熺湅娓呮涓よ呴鐩殑涓嶅悓錛?
鍋囧鏈変笁縐嶇墿鍝侊紝鑳屽寘鍙50紓呯殑鐗╁搧錛岀墿鍝?閲?0紓咃紝浠峰?0鍏冿紱鐗╁搧2閲?0紓咃紝浠峰?00鍏冿紱鐗╁搧3閲?0紓咃紝浠峰?20鍏冦傚洜姝わ紝鏃㈢劧鍙互閫夋嫨鍙涓閮ㄥ垎錛屾垜浠彲浠ョ畻鍑烘瘡縐嶇墿鍝佺殑鍗曚綅浠峰鹼紝鐗╁搧1鏄瘡紓?鍏冿紝鐗╁搧2鏄編閭?鍏冿紝鐗╁搧3鏄瘡紓?鍏冦傛寜鐓ц椽蹇?jī)绛栫暐锛屽簲璇ョ幇鐘剁墿鍝?錛屽鏋滆瀹岀墿鍝?鑳屽寘榪樻湁絀洪棿錛屽啀瑁呯墿鍝?……
鏈鍚庣殑緇撴灉鏄細(xì)
鑰屽鏋滄寜01鑳屽寘錛屽垯緇撴灉鏄細(xì)
鏈夊叴瓚ｇ殑鍙互鎷挎垜閭?1鑳屽寘鐨勭▼搴忓幓楠岃瘉榪欎釜緇撴灉銆?/p>
涓嬮潰鏄竴涓儴鍒嗚儗鍖呯殑灝忕▼搴忥細(xì)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <algorithm> using namespace std; typedef struct Thing{ double v; // value double w; // weight }Thing; Thing arr[100]; int n; double W; bool cmp(Thing a, Thing b) { return a.v/a.w > b.v/b.w; } int main() { cout << "杈撳叆鐗╁搧涓暟: "; cin >> n; cout << "杈撳叆鑳屽寘鍙澆閲嶉噺: "; cin >> W; cout << "杈撳叆" << n << "涓墿鍝佺殑浠峰煎拰閲嶉噺:" << endl; for(int i=0; i<n; ++i) cin >> arr[i].v >> arr[i].w; sort(arr, arr+n, cmp); int k = 0; double value = 0; while(W) { if(W >= arr[k].w) { W -= arr[k].w; value += arr[k].v; } else { value += W * arr[k].v / arr[k].w; W = 0; } ++k; } cout << "鏈澶т環(huán)鍊兼槸: " << value << endl; return 0; } |
緇撴灉濡傚浘錛?/p>
]]>
棣栧厛璇翠竴涓嬶紝ACM鐨勫叆闂ㄦ柟娉曞縐嶅鏍鳳紝澶ч儴鍒嗕漢榪樻槸璺熺潃瀛︽牎涓璧峰弬鍔犻泦璁紝鎵浠ユ垜榪欓噷涓昏鏄兂瀵歸偅浜涘噯澶嘇CM鍏ラ棬鐨勪笟浣欑殑鏈嬪弸璋堢殑銆?/p>
鍏ラ棬涔︾睄錛?/p>
棣栧厛鎺ㄨ崘涓浜汚CM鐨勪功綾嶏細(xì)
(浠ヤ笅鎴戦兘浼?xì)缁欏嚭鍦ㄥ綋褰摼|戠殑欏甸潰錛屾柟渚垮ぇ瀹剁洿鎺ヨ喘涔幫紝浠ヤ笅鎺掑悕涓嶅垎鍏堝悗)
1.銆婄▼搴忚璁″寮曞強(qiáng)鍦ㄧ嚎瀹炶返銆?br />http://product.dangdang.com/product.aspx?product_id=20051430&ref=search-1-pub
榪欐槸鎴戠殑絎竴鏈叆闂ㄤ功錛岃繖鏈功鏄厤濂楀寳澶х殑鐧劇偧涔?fàn)棰樺Q屾敞鎰忎笉鏄疨OJ錛岃矊浼兼槸鍖楀ぇ鍐呴儴嫻嬭瘯鐢ㄧ殑錛屼笉榪囦篃鏄澶栧紑鏀劇殑錛屽幓騫村ソ鍍忕櫨鐐煎彉鍖栬繃錛屾墍浠u]涓嶇煡閬撹繖鏈功榪橀備笉閫傚悎閭ｄ釜鏂扮殑鐧劇偧緋葷粺[/u]銆?/p>
2.銆婄畻娉曠珵璧涘叆闂ㄧ粡鍏搞?br />http://product.dangdang.com/product.aspx?product_id=20724029&ref=search-1-pub
榪欐湰涔︽病璇濊錛屽垬姹濅匠鐨勭櫧涔︼紝緇忓吀鐨勭畻娉曞叆闂ㄤ功綾嶃俒b]寮虹儓鎺ㄨ崘[/b]錛?/p>
3.銆婄畻娉曡壓鏈笌淇℃伅瀛︾珵璧涖?br />http://product.dangdang.com/product.aspx?product_id=8811386&ref=search-1-pub
鍒樻睗浣崇殑榛戜功錛岄毦搴﹁緝娣憋紝棰樼洰鍩烘湰鏉ヨ嚦Uva錛屾垜鏄湅浜?jiǎn)鍓嶉潰浠ラ儴鍒嗗Q屽悗闈㈠氨娌″拫鐪嬩簡(jiǎn)銆傘傘?/p>
4.銆婄畻娉曞璁恒?br />http://product.dangdang.com/product.aspx?product_id=9211884&ref=search-1-pub
緇忓吀鐨勪功綾嶆槸涓嶉渶瑕佽В閲婄殑銆?br />榪欐槸鎴戞浘緇忎笂浼犺繃鐨勮嫳鏂囩増CHM綆楁硶瀵艱錛屽彲浠ヤ笅杞戒簡(jiǎn)鐪嬬湅錛?br />http://www.cppleyuan.com/viewthread.php?tid=5130&highlight=%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA
鎴戞渶榪戜篃鍦ㄥ啓綆楁硶瀵艱鐨勮涔︽葷粨錛屾榪庡ぇ瀹舵帰璁細(xì)
http://www.wutianqi.com/?p=2403
5.銆婄紪紼嬩箣緹庛?br />http://product.dangdang.com/product.aspx?product_id=20170952&ref=search-1-pub
鎸烘湁鎰忔濈殑錛屼笉鑳戒綔涓轟竴涓畻娉曠殑鍏ㄩ潰涔︾睄錛岃屾槸浣滀負(fù)涓鏈嫇瀹芥濈淮鐨勪功綾嶏紝鏈夊叴瓚ｇ殑寤鴻瑕佺湅鐪嬨?/p>
6.銆婅綆楁満紼嬪簭璁捐鑹烘湳銆?br />http://product.dangdang.com/product.aspx?product_id=690222&ref=search-1-pub
鏈夊ソ鍑犲嵎鐨勶紝鍙粰鍑轟竴鍗風(fēng)殑榪炴帴錛岃屼笖緗戜笂鐗堟湰寰堝錛屽ぇ瀹跺彲浠ヨ嚜琛岄夋嫨銆?br />榪欎釜榪樻病鐪嬶紝鍏抽敭鏄病鏃墮棿浜?jiǎn)锛屽噯澶囪冪爺瀹屼簡(jiǎn)灝辮秮鐫鍋囨湡鐪嬪畬銆?/p>
7.銆婄粍鍚堟暟瀛︺?br />http://product.dangdang.com/product.aspx?product_id=8976756&ref=search-0-mix
楦藉發(fā)鍘熺悊錛屽崥寮堬紝瀹規(guī)枼鍘熺悊錛孋atalan鏁扮瓑閮藉睘浜庤繖涓寖鐣寸殑錛屽緩璁湅鐪嬨?/p>
8.銆婃暟鎹粨鏋勶紙C璇█鐗堬級(jí)銆嬩弗钄氭晱
http://product.dangdang.com/product.aspx?product_id=9268172&ref=search-1-pub
鏁版嵁緇撴瀯錛岃繖涓繀欏誨緱瀛﹀ソ鍟妦~~
9.銆婃暟鎹粨鏋勪笌綆楁硶鍒嗘瀽C++鎻忚堪錛堢涓夌増錛夈?br />http://product.dangdang.com/product.aspx?product_id=9239535&ref=search-1-pub
鏈夋椂闂村彲浠ョ湅鐪嬶紝C++ Template鍐欑殑錛屽彲浠ラ『渚垮琺鍥轟笅template銆?/p>
浠ヤ笅鍩烘湰閮芥病鐪嬭繃錛屼笉榪囪矊浼煎緢鏈夊悕錛岀粰鍑轟功鍚嶅拰榪炴帴錛?br />10.銆婁笘鐣屽ぇ瀛︾敓紼嬪簭璁捐绔炶禌錛圓CM/ICPC錛夐珮綰ф暀紼?絎竴鍐?紼嬪簭璁捐涓父鐢ㄧ殑璁＄畻鎬濈淮鏂瑰紡銆?br />http://product.dangdang.com/product.aspx?product_id=20645866&ref=search-1-pub
榪欐湰鎴戝叾瀹炰拱浜?jiǎn)锛屼絾鏄瘶q樻病鏈夋椂闂寸湅銆?/p>
11.銆婂浗闄呭ぇ瀛︾敓紼嬪簭璁捐绔炶禌鎸囧崡—ACM紼嬪簭璁捐銆?br />http://product.dangdang.com/product.aspx?product_id=20450827&ref=search-1-pub
12.銆婂浗闄呭ぇ瀛︾敓紼嬪簭璁捐绔炶禌渚嬮瑙ｏ紙涓夛級(jí)鍥捐銆佸姩鎬佽鍒掔畻娉曘佺患鍚堥?shù)笓闆嗐?br />http://product.dangdang.com/product.aspx?product_id=9352432&ref=search-1-pub
榪欎釜濂藉儚涔熸湁濂藉嚑鍐岋紝姣忎竴鍐岄兘鏄崟鐙涓涓柟闈㈢殑銆?/p>
13.銆婃寫鎴樼紪紼嬶細(xì)紼嬪簭璁捐绔炶禌璁粌鎵嬪唽銆?br />http://product.dangdang.com/product.aspx?product_id=20637355&ref=search-1-pub
(浣滆咃細(xì)Tanky Woo, 涓漢鍗氬錛?/span>http://www.wutianqi.com 錛孋++/綆楁硶璁哄潧錛?/span>http://www.cppleyuan.com/ 銆傝漿杞借娉ㄦ槑涓漢鍙?qiáng)鍘熸枃杩炴帴锛岃阿璋㈠悎浣?
鍏ラ棬鏂規(guī)硶錛?br />榪欎箞澶氫功錛屼笉鍙兘鍏ㄩ儴閮界湅鐨勶紝鎴戣寰楀墠10鏈紝涔熷氨鏄垜鐪嬭繃鐨勶紝閮借繕?shù)笉閿欏Q屽ぇ瀹跺彲浠ョ湅鐪嬨?br />鍙﹀錛屾垜涓漢鎺ㄨ崘ACM鍙互榪欐牱鍏ラ棬(浠ヤ笅鐢ㄥ埌浜?jiǎn)涓婇潰涔c嶅墠闈㈢殑搴忓彿)錛氾紙褰撶劧錛屽鏋滃鏍℃湁涓撻棬鍩硅鐨勶紝鍒欒窡鐫瀛︽牎鏉ユ洿濂斤級(jí)
1.鏁版嵁緇撴瀯鏄熀紜錛屽緩璁厛鎶?鍙蜂弗钄氭晱鑰佸笀鐨勩婃暟鎹粨鏋勩嬪ソ濂界湅1~2閬嶏紝浠ｇ爜閮芥墜鍔ㄦ暡涓鏁層?br />2.鍐嶇湅2鍙?strong>鍒樻睗浣崇殑鐧戒功銆?br />3.鍘誨勾鏆戝亣(2010.7~2010.9鏈?錛屾垜鏇劇粡緇欐垜鐨勮鍧?C++濂嬫枟涔愬洯錛?a title="http://www.cppleyuan.com/" style="color: rgb(49,52,40); text-decoration: none" >http://www.cppleyuan.com/)鎼炶繃涓嬈?strong>ACM涓撻璁粌錛岃緇冮鍏ㄩ儴鏉ヨ嚦HDOJ錛屽綋鏃舵垜鏄敱鏄撳埌闅撅紝姣忓ぉ閫夋嫨涓涓笓棰橈紝鍦℉DOJ涓婃壘3~4棰橈紝鐒跺悗鍦ㄨ鍧涚粰鍑洪鐩紝澶у鍙互鍒癏DOJ鍘繪彁浜わ紝鐒跺悗璐村埌璁哄潧渚涘叾浠栨湅鍙嬪弬鑰冦傛澘鍧楁槸錛?a style="color: rgb(49,52,40); text-decoration: none" >http://www.cppleyuan.com/forumdisplay.php?fid=40錛屽墠闈㈤兘鏄湅涔︼紝榪欓噷灝卞緩璁ぇ瀹跺紑濮嬪疄鎴樹(shù)簡(jiǎn)錛屽湪璁哄潧閲屼竴鍏遍櫎浜?00澶氶錛屽ぇ瀹朵竴瀹氳鍋氾紒
4.鏈変簡(jiǎn)涓瀹氱殑鍩虹錛屽氨鍙互鍐?strong>涓杈硅繘琛屾繁鍏?鐪嬩功)錛屼竴杈瑰仛棰?/strong>浜?jiǎn)銆傝繖涓椂鍊欑椹婄畻娉曞璁恒嬶紝銆婅綆楁満紼嬪簭璁捐鑹烘湳銆嬬瓑絳夐兘鍙互鐪嬬湅銆?br />5.鍒頒簡(jiǎn)榪欎釜闃舵錛屾病鍟ヨ鐨勪簡(jiǎn)錛?strong>鑷敱瀛︿範(fàn)~~~
鏈鍚庤涓鍙ワ細(xì)綆楁硶欖呭姏錛屾棤涓庝雞姣旓紝嬈㈣繋澶у鏉ュ埌ACM鐨勪笘鐣岋紒鍔犳補(bǔ)錛?/p>
(浣滆咃細(xì)Tanky Woo, 涓漢鍗氬錛?a style="color: rgb(49,52,40); text-decoration: none" >http://www.wutianqi.com 錛孋++/綆楁硶璁哄潧錛?a title="http://www.cppleyuan.com/" style="color: rgb(49,52,40); text-decoration: none" >http://www.cppleyuan.com/ 銆傝漿杞借娉ㄦ槑涓漢鍙?qiáng)鍘熸枃杩炴帴锛岃阿璋㈠悎浣?
]]>
寤鴻鍏堢湅鐪嬪墠璦錛?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
榪欎釜妗堜緥涔熸瘮杈冪畝鍗曪紝鏈闀垮叕鍏卞瓙搴忓垪(LCS)錛岀綉涓婄殑鍒嗘瀽闈炲父澶氾紝緇欏姏鍟婏紒
鎸夌収涓婁竴綃囨葷粨鎵璇寸殑錛屾壘鐘舵佽漿縐繪柟紼嬶細(xì)
鎵浠ユ寜鐓ф墍緇?a style="color: rgb(49,52,40); text-decoration: none" >鏂圭▼錛屽啓浠ｇ爜鐨勫伐浣滃氨闈炲父闈炲父綆鍗曡交鏉句簡(jiǎn)錛?/p>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
/* Author: Tanky Woo Blog: www.WuTianQi.com About: 銆婄畻娉曞璁恒?5.4 鏈闀垮叕鍏辮嚜搴忓垪(LCS) */ #include <iostream> using namespace std; char b[20][20]; int c[20][20]; char x[20], y[20]; void LCS() { int m = strlen(x+1); int n = strlen(y+1); for(int i=1; i<=m; ++i) c[i][0] = 0; for(int j=1; j<=n; ++j) c[0][j] = 0; for(int i=1; i<=m; ++i) for(int j=1; j<=n; ++j) { if(x[i] == y[j]) { c[i][j] = c[i-1][j-1] + 1; b[i][j] = '\\'; // 娉ㄦ剰榪欓噷絎竴涓猏\鏄漿縐誨瓧絎︼紝浠ｈ〃\ } else if(c[i-1][j] >= c[i][j-1]) { c[i][j] = c[i-1][j]; b[i][j] = '|'; } else { c[i][j] = c[i][j-1]; b[i][j] = '-'; } } } void printLCS(int i, int j) { if(i == 0 || j == 0) return; if(b[i][j] == '\\') { printLCS(i-1, j-1); cout << x[i] << " "; } else if(b[i][j] == '|') printLCS(i-1, j); else printLCS(i, j-1); } int main() { cout << "Input the array A:\n"; cin >> x+1; cout << "Input the array B:\n"; cin >> y+1; LCS(); printLCS(strlen(x+1), strlen(y+1)); } |
鐪嬩功涓婂浘15-6鐨勭粨鏋滃浘錛?/p>
鍙堟槸涓涓粰鍔涚殑鍥?寤鴻鑷繁鎸夌収紼嬪簭鎶婅繖涓浘鐢誨嚭鏉?
鍙﹀,璇村埌LCS,涓嶅緱涓嶈鐨勬槸LIS(鏈闀夸笂鍗囧瓙搴忓垪)錛屼篃鏄竴涓狣P錛屾垜鏇劇粡鎬葷粨榪囷細(xì)
http://www.wutianqi.com/?p=1850
鍦ㄦ垜鐙珛鍗氬涓婄殑鍘熸枃錛?a >http://www.wutianqi.com/?p=2505
嬈㈣繋澶у浜掔浉瀛︿範(fàn)錛屼簰鐩歌繘姝ワ紒
]]>
寤鴻鍏堢湅鐪嬪墠璦錛?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
榪欎竴鑺傚彲浠ョ湅鍒?a style="color: rgb(49,52,40); text-decoration: none" >銆婄畻娉曞璁恒嬪涔?fàn)鎬葷粨 — 16.絎?5绔?鍔ㄦ佽鍒?1) 鍩烘湰鍏ラ棬鐨勮ˉ鍏呫?/p>
閲囩敤鍔ㄦ佽鍒掔殑鏈浼樺寲闂鐨勪袱涓绱狅細(xì)鏈浼樺瓙緇撴瀯鍜?strong>閲嶅彔瀛愰棶棰?/font>銆?/font>
鍏堢湅鐪嬫渶浼樺瓙緇撴瀯錛?/p>
鍦ㄧ17綃囨葷粨鏃訛紝瑁呴厤綰胯皟搴﹂棶棰樹(shù)腑錛屽凡緇忚璁″埌浜?jiǎn)鏈浼樺瓙緇撴瀯錛岃瘉鏄庢渶浼樺瓙緇撴瀯闂鍙互鐢ㄤ功涓婅鐨?#8220;鍓創(chuàng)鎶鏈?#8221;錛屽嵆鍋囪瀛樺湪鏇翠紭鐨勮В錛屾潵鍙嶆鏈浼樿В鐭涚浘銆?/p>
鍐嶇湅鐪嬮噸鍙犲瓙闂錛?/p>
褰撲竴涓掑綊綆楁硶涓嶆柇鐨勮皟鐢ㄥ悓涓涓棶棰樻椂錛屾垜浠璇ユ渶鏈夐棶棰樺寘鍚?#8220;閲嶅彔瀛愰棶棰?#8221;銆?/p>
涓婇潰榪欏彞璇濅笉濂界悊瑙ｏ紵
鐪嬬湅涓嬮潰榪欎釜姣旇緝錛?/p>
閫掑綊綆楁硶錛氳嚜欏惰屼笅錛屽鍦ㄩ掑綊鏍?wèi)涓噸澶嶅嚭鐜扮殑姣忎釜瀛愰棶棰橀兘瑕侀噸澶嶈В涓嬈°?/p>
鍔ㄦ佽鍒掞細(xì)鑷笅鑰屼笂錛屽姣忎釜鍙В涓嬈°?/p>
緇撳悎絎?6綃囨葷粨鐨勪笁瑙掑艦姹傚間緥瀛愶紝鍙互鐪嬪緱鍒幫紝鑷笅鑰屼笂瀵艱嚧姣忎釜瀛愰棶棰樺彧姹傝В涓嬈°?/p>
浠ヤ笂鐞嗚鎬ф湁鐐瑰己錛屾垜鏈寮濮嬪DP鐪嬬殑鏄疕DOJ鐨勮浠訛紝鏈夊叴瓚ｇ殑鍙互鍘葷湅鐪嬨?/p>
鍦ㄩ偅閲岄潰錛屼富瑕佽鍒頒簡(jiǎn)鏄壘鐘舵佽漿縐繪柟紼嬶紝鍦ㄧ16綃囩殑涓夎褰㈡眰鍊間緥瀛愬拰絎?7綃囩殑瑁呴厤綰胯皟搴︿緥瀛愶紝閭ｄ簺閫掑綊鍏紡閮芥槸鐘舵佽漿縐繪柟紼嬨?/p>
涓嬮潰榪欐璇濆ソ濂界悊瑙ｏ細(xì)
——————————————————————–
鍔ㄦ佽鍒掔殑鍑犱釜姒傚康:
闃舵錛氭嵁絀洪棿欏哄簭鎴栨椂闂撮『搴忓闂鐨勬眰瑙ｅ垝鍒嗛樁孌點(diǎn)?span class="Apple-converted-space">
鐘舵侊細(xì)鎻忚堪浜嬬墿鐨勬ц川錛屼笉鍚屼簨鐗╂湁涓嶅悓鐨勬ц川錛屽洜鑰岀敤涓嶅悓鐨勭姸鎬佹潵鍒葷敾銆傚闂鐨勬眰瑙ｇ姸鎬佺殑鎻忚堪鏄垎闃舵鐨勩?span class="Apple-converted-space">
鍐崇瓥錛氭牴鎹鎰忚姹傦紝瀵規(guī)瘡涓樁孌墊墍鍋氬嚭鐨勬煇縐嶉夋嫨鎬ф搷浣溿?span class="Apple-converted-space">
鐘舵佽漿縐繪柟紼嬶細(xì)鐢ㄦ暟瀛﹀叕寮忔弿榪頒笌闃舵鐩稿叧鐨勭姸鎬侀棿鐨勬紨鍙樿寰嬨?/p>
鍔ㄦ佽鍒掓槸榪愮瀛︾殑涓涓噸瑕佸垎鏀紝鏄В鍐沖闃舵鍐崇瓥榪囩▼鏈浼樺寲鐨勪竴縐嶆柟娉曘?/p>
鎵璋撳闃舵鍐崇瓥榪囩▼錛屾槸灝嗘墍鐮旂┒鐨勮繃紼嬪垝鍒嗕負(fù)鑻ュ共涓浉浜掕仈緋葷殑闃舵錛屽湪姹傝В鏃訛紝瀵規(guī)瘡涓涓樁孌甸兘瑕佸仛鍑哄喅絳栵紝鍓嶄竴涓喅絳栫‘瀹氫互鍚庯紝甯稿父浼?xì)濯?jiǎng)鍝嶄笅涓涓樁孌電殑鍐崇瓥銆?/p>
鍔ㄦ佽鍒掓墍渚濇嵁鐨勬槸“鏈浼樻у師鐞?#8221;銆?span class="Apple-converted-space">
“鏈浼樻у師鐞?#8221;鍙檲榪頒負(fù)錛氫笉璁哄垵濮嬬姸鎬佸拰絎竴姝ュ喅絳栨槸浠涔堬紝浣欎笅鐨勫喅絳栫浉瀵逛簬鍓嶄竴嬈″喅絳栨墍浜х敓鐨勬柊鐘舵侊紝鏋勬垚涓涓渶浼樺喅絳栧簭鍒椼?/p>
鏈浼樺喅絳栧簭鍒楃殑瀛愬簭鍒楋紝涓瀹氭槸灞閮ㄦ渶浼樺喅絳栧瓙搴忓垪銆?span class="Apple-converted-space">
鍖呭惈鏈夐潪灞閮ㄦ渶浼樼殑鍐崇瓥瀛愬簭鍒楋紝涓瀹氫笉鏄渶浼樺喅絳栧簭鍒椼?/p>
鍔ㄦ佽鍒掔殑鎸囧鎬濇兂鏄細(xì)
鍦ㄥ仛姣忎竴姝ュ喅絳栨椂錛屽垪鍑哄悇縐嶅彲鑳界殑灞閮ㄨВ錛屼箣鍚庝緷鎹煇縐嶅垽瀹氭潯浠訛紝鑸嶅純閭ｄ簺鑲畾涓嶈兘寰楀埌鏈浼樿В鐨勫眬閮ㄨВ銆傝繖鏍鳳紝鍦ㄦ瘡涓姝ラ兘緇忚繃絳涢夛紝浠ユ瘡涓姝ラ兘鏄渶浼樼殑鏉ヤ繚璇佸叏灞鏄渶浼樼殑銆傜瓫閫夌浉褰撲簬鏈澶ч檺搴﹀湴鏈夋晥鍓灊錛堜粠鎼滅儲(chǔ)瑙掑害鐪嬶級(jí)錛屾晥鐜囦細(xì)鍗佸垎楂樸備絾瀹冨張涓嶅悓浜庤椽蹇?jī)娉曘傝椽蹇?jī)娉曞彧鑳藉仛鍒板眬閮ㄦ渶浼橈紝涓嶈兘淇濊瘉鍏ㄥ眬鏈浼橈紝鍥犱負(fù)鏈変簺闂?shù)笉绗﹀悎鏈浼樻у師鐞嗐?/font>
——————————————————————–
鐪嬭鏈変漢璇撮掑綊灝辨槸DFS錛岃孌P灝辨槸BFS錛屾劅瑙夋湁閭ｄ箞涓鐐規(guī)剰鎬濓紝瀵逛簬DP錛屽氨鏄粠搴曞眰涓灞傚眰鐨勮綆楋紝鐒跺悗鍦ㄥ綋灞備腑閫夊彇鏈浼橈紝閫愬眰鏈浼樹(shù)互鑷蟲(chóng)諱綋鏈浼樸?/p>
鍏跺疄榪欎釜榪樻槸澶氬仛涓浜涢灝卞ソ浜?⊙锝?#8857;)錛屽ぇ瀹跺埆璁や負(fù)鎴戞槸鍋氶鎺э紝鍏跺疄璇村疄鍦ㄨ瘽錛岀湅N閬嶄笉濡傚仛涓棰橈紝璇寸櫧浜?jiǎn)锛尳帡娉曟暟瀛︽湰涓瀹訛紝綆楁硶灝辨槸鏁板錛岃蛋榪囬珮?shù)腑鐨勫Q岄兘鐭ラ亾鏁板棰樺緱澶氬仛錛屽挨鍏跺帇杞撮錛岀湅N閬嶄笉濡傚仛涓閬嶏紝榪欎釜涔熸槸涓鏍峰仛鍑犻灝辯煡閬揇P鏄椹笢涓滀簡(jiǎn)錛?/p>
鍦ㄦ垜鐙珛鍗氬涓婄殑鍘熸枃錛?a >http://www.wutianqi.com/?p=2500
嬈㈣繋澶у浜掔浉瀛︿範(fàn)錛屼簰鐩歌繘姝ワ紒
]]>
寤鴻鍏堢湅鐪嬪墠璦錛?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
鍘熸潵鎵撶畻鎶婄畻娉曞璁哄湪7鏈堜喚鍓嶆悶瀹氾紝鐜板湪宸茬粡榪囧幓涓涓鏈堜簡(jiǎn)錛屾墠鍙湅鍒扮15绔狅紝鍚庨潰涔熷彧闆舵暎鐪嬩簡(jiǎn)涓浜涳紝涓嶇煡閬撳亣鏈熷墠鑳藉惁鐪嬪畬銆傘傘傚鍛涘晩錛岄┈涓婅鏈熸湯鑰冭瘯浜?jiǎn)锛屼笂瀛︽湡GPA涓嶅埌2錛岃瀛︿綅璀﹀憡浜?jiǎn)锛岃櫧璇翠互鍚庝笉瀛q欎釜涓撲笟浜?jiǎn)锛屼絾钃v鐮佹垚緇╁崟涓婁篃涓嶈兘鏈夋寕縐戞槸鍚с傘傘傝鏄鉤鏃朵竴鐐逛笉鐪嬶紝鑰冨墠闈犳槬鍝ワ紝鏇懼摜錛屽叧鍏摜閮戒笉琛屽晩銆傘傘傝繖榪涘害錛岄儊闂鳳紒
灝藉姏鍚э紒
欏轟究榪樻槸璇翠袱鍙ヨ瘽錛?/p>
1.鏈変簺涔︿笂鍒嗘瀽鐨勭浉褰撳ソ浜?jiǎn)锛屾垜涓嶆儧_仛鐢昏泧娣昏凍鐨勪漢錛屾墍浠ユ湁鐨勫湴鏂規(guī)垜浼?xì)閫傚綋鐪佺暐錛屽綋鐒朵篃涓嶆槸璇存垜鎬葷粨鐨勫湴鏂瑰氨鏄功涓婅鐨勪笉濂界殑鍦版柟錛屽彧鏄病浜烘湁涓濂楄嚜宸辯殑鐞嗚В鏂瑰紡錛屾垜鐢ㄨ嚜宸辯殑璇濆幓鎬葷粨浜?jiǎn)锛屽綋鏃朵篃灏辨槸鏈閫傚悎鎴戠殑鐭ヨ瘑錛佹墍浠ワ紝寤鴻澶у澶氬啓涓浜涚畻娉曟葷粨錛屼綘浼?xì)浣撲細(xì)鍒板ソ澶勭殑锛?/p>
2.鑰屼笖鎴戣繖涓殑鎬ц川鏄葷粨錛屼笉鏄涓涓畻娉曠殑鍏蜂綋璁茶В錛屾墍浠ヤ笉鍏堢湅涔︼紝澶у搴旇璇諱笉鎳傜殑錛屽氨姣斿涓嬮潰錛岄鐩垜灝辨病鏈夎創(chuàng)鍑烘潵錛屽ぇ瀹朵笉鐪嬫暟錛岃偗瀹氬氨璇諱笉鎳傦紝鎴戠殑鐩殑鏄ぇ瀹剁湅瀹屼功鍚庯紝璋㈣阿鎬葷粨錛屾垨鑰呯湅鐪嬪埆浜哄啓鐨勬葷粨錛岃涓嶅畾鍙互鍙戠幇鑷繁鍝簺鍦版柟鐞嗚В閿欎簡(jiǎn)錛屽摢浜涘湴鏂逛笉鐞嗚В錛屾垨鏄摢浜涘湴鏂瑰煎緱鎺㈣銆?/p>
寤鴻鍏堢湅鐪嬪墠璦錛?a title="http://www.wutianqi.com/?p=2298" style="color: rgb(49,52,40); text-decoration: none" >http://www.wutianqi.com/?p=2298
榪欎竴嬈′富瑕佹槸鍒嗘瀽15.1鑺傜殑渚嬪瓙—瑁呴厤綰胯皟搴﹂棶棰樸?/p>
棰樼洰鏈夌偣闀匡紝棣栧厛寰楁妸棰樼洰璇繪噦銆?/p>
榪欎釜渚嬪瓙涔︿笂鑺變簡(jiǎn)6闈㈢焊鐨勭瘒騫呮潵璇︾粏鍒嗘瀽錛岀敱姝ゅ彲瑙佸叾閲嶈鎬с?/p>
璋堝埌DP,涓嶅緱涓嶈鐨勫氨鏄毚鍔涙硶錛屽ぇ瀹墮兘鐭ラ亾錛屽鏋滅敤鏆村姏瑙ｅ喅綾諱技闂錛屼竴鑸椂闂村鏉傚害閮芥槸闈炲父闈炲父鐨勯珮錛岃繖涓椂鍊欐晳涓栦富DP灝卞嚭鏉ヤ簡(jiǎn)錛孌P浠ラ伩鍏嶄簡(jiǎn)璁稿閲嶅鐨勮綆楋紝鑰屽ぇ澶ч檷浣庝簡(jiǎn)鏃墮棿澶嶆潅搴︺?/p>
鎸夌収涔︿笂鐨勫洓涓楠わ紝鎴戝湪榪欓噷鎻愬彇涓浜涢噸鐐癸紝寤鴻榪樻槸鎶奝194~196榪欏洓姝ュ畬鏁存楠ょ湅涔︿笂鐨勫垎鏋愩傚彧鏈夋參鎱㈠搧鍛籌紝浣犳墠浼?xì)鍙戠幇銆婄畻娉曞璁恒嬬殑緹庛?/p>
姝ラ涓錛?/p>
鍒嗘瀽闂錛屾瘮濡備竴涓簳鐩樿鍒拌揪S[1][j]錛屽垯鏈変袱縐嶆儏鍐碉紝絎竴縐嶆槸浠嶴[1][j-1]鍒癝[1][j]錛岀浜岀鏄粠S[2][j-1]鍒癝[1][j]銆傛壘鍑?guó)櫩欎袱鑰呮墍鑺辨椂闂寸殑鏈灝忥紝鍒欏氨鏄疭[1][j]鎵闇鏃墮棿鐨勬渶灝忋?/p>
榪欏氨鏄湁灞閮ㄦ渶浼樿В姹傚叏灞鏈浼樿В銆備篃灝辨槸璇達(dá)紝涓涓棶棰樼殑鏈浼樿В鍖呭惈浜?jiǎn)瀛愰棶棰樼殑涓涓渶浼樿В銆傛垜浠О榪欎釜鎬ц川涓烘渶浼樺瓙緇撴瀯銆傝繖鏄槸鍚﹀彲浠ュ簲鐢―P鐨勬爣蹇椾箣涓銆?/p>
姝ラ浜?/strong>錛?/p>
鎵懼嚭榪欎釜閫掑綊鍏崇郴錛岀敱姝ラ涓鍙互寰楀埌榪欎釜閫掑綊鍏崇郴錛?/p>
姝ラ涓?/strong>錛?/p>
鍥犱負(fù)閫掑綊鐨勫叧緋伙紝涓鑸繪槸鍙互杞崲涓洪潪閫掑綊鐨勭畻娉曘?/p>
鐢卞凡鐭ラ噺f1[1], f2[1]閫愭鎺ㄥ嚭鏈煡閲忥紝鎺ㄥ晩鎺紝鎺ㄥ晩鎺紝鏈鍚庡氨鎺ㄥ埌緇撴灉浜?jiǎn)~~~~ 姝ラ鍥?/strong>錛?/p>
鍐嶇敱宸茬煡緇撴灉榪斿洖姹傝礬寰勩?/p>
榪欎竴鑺傛渶緇欏姏鐨勫氨鏄繖涓緥瀛愪互鍙?qiáng)鐩稿簲鐨?strong>鍥?/strong>錛?/p>
鎷胯搗絎旓紝鐢ㄤ功涓婄粰鍑虹殑渚嬪瓙錛屽垎鏋愯繖涓浘錛?/p>
浠ヤ笅鏄唬鐮侊細(xì) 鏈鍚庤繕鏄鎰熷徆涓涓嬶紝銆婄畻娉曞璁恒嬭鐨勭湡鏄鏋佷簡(jiǎn)錛屽笇鏈涘ぇ瀹惰兘闈?rùn)涓嬪績(jī)鎶姌q欎竴绔犺妭濂藉ソ鐪嬬湅銆?br /> 鍦ㄦ垜鐙珛鍗氬涓婄殑鍘熸枃錛?a >http://www.wutianqi.com/?p=2496 嬈㈣繋澶у浜掔浉瀛︿範(fàn)錛屼簰鐩歌繘姝ワ紒
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
Author: Tanky Woo
Blog: www.WuTianQi.com
About: 銆婄畻娉曞璁恒?5.1 瑁呴厤綰胯皟搴?
*/
#include <iostream>
using namespace std;
int n; // 涓涓閰嶇嚎涓婃湁n涓閰嶇珯
int e1, e2; // 榪涘叆瑁呴厤綰?,2闇瑕佺殑鏃墮棿
int x1, x2; // 紱誨紑瑁呴厤綰?,2闇瑕佺殑鏃墮棿
int t[3][100]; // t[1][j]琛ㄧず搴曠洏?shù)粠S[1][j]縐誨姩鍒癝[2][j+1]鎵闇鏃墮棿,鍚岀悊t[2][j]
int a[3][100]; // a[1][j]琛ㄧず鍦ㄨ閰嶇珯S[1][j]鎵闇鏃墮棿
int f1[100], f2[100]; // f1[j], f2[j]鍒嗗埆琛ㄧず鍦ㄧ涓/絎簩鏉¤閰嶇嚎涓婄j涓閰嶇珯鐨勬渶浼樿В
int ln1[100], ln2[100];// ln1[j]璁板綍絎竴鏉¤閰嶇嚎涓?鏈浼樿В鏃剁j涓閰嶇珯鐨勫墠涓涓閰嶇珯鏄涓鏉＄嚎榪樻槸絎簩鏉＄嚎涓?/span>
int f, ln; // 鏈浼樿В鏄?f浠ｈ〃鏈灝忚姳璐規(guī)椂闂達(dá)紝ln琛ㄧず鏈鍚庡嚭鏉ユ椂鏄粠瑁呴厤綰?榪樻槸瑁呴厤綰?
void DP()
{
f1[1] = e1 + a[1][1];
f2[1] = e2 + a[2][1];
for(int j=2; j<=n; ++j)
{
// 澶勭悊絎竴鏉¤閰嶇嚎鐨勬渶浼樺瓙緇撴瀯
if(f1[j-1] + a[1][j] <= f2[j-1] + t[2][j-1] + a[1][j])
{
f1[j] = f1[j-1] + a[1][j];
ln1[j] = 1;
}
else
{
f1[j] = f2[j-1] + t[2][j-1] + a[1][j];
ln1[j] = 2;
}
// 澶勭悊絎簩鏉¤閰嶇嚎鐨勬渶浼樺瓙緇撴瀯
if(f2[j-1] + a[2][j] <= f1[j-1] + t[1][j-1] + a[2][j])
{
f2[j] = f2[j-1] + a[2][j];
ln2[j] = 2;
}
else
{
f2[j] = f1[j-1] + t[1][j-1] + a[2][j];
ln2[j] = 1;
}
}
if(f1[n] + x1 <= f2[n] + x2)
{
f = f1[n] + x1;
ln = 1;
}
else
{
f = f2[n] + x2;
ln = 2;
}
}
void PrintStation()
{
int i= ln;
cout << "line " << i << ", station " << n << endl;
for(int j=n; j>=2; --j)
{
if(i == 1)
i = ln1[j];
else
i = ln2[j];
cout << "line " << i << ", station " << j-1 << endl;
}
}
int main()
{
//freopen("input.txt", "r", stdin);
cout << "杈撳叆瑁呴厤绔欑殑涓暟: ";
cin >> n;
cout << "杈撳叆榪涘叆瑁呴厤綰?錛?鎵闇鐨勬椂闂磂1, e2 :";
cin >> e1 >> e2;
cout << "杈撳叆紱誨紑瑁呴厤綰?, 2鎵闇鐨勬椂闂磝1, x2: ";
cin >> x1 >> x2;
cout << "杈撳叆瑁呴厤綰?涓婂悇绔欏姞宸ユ墍闇鏃墮棿a[1][j]: ";
for(int i=1; i<=n; ++i)
cin >> a[1][i];
cout << "杈撳叆瑁呴厤綰?涓婂悇绔欏姞宸ユ墍闇鏃墮棿a[2][j]: ";
for(int i=1; i<=n; ++i)
cin >> a[2][i];
cout << "杈撳叆瑁呴厤綰?涓婄殑绔欏埌瑁呴厤綰?涓婄殑绔欐墍闇鏃墮棿t[1][j]: ";
//娉ㄦ剰榪欓噷鏄痠<n錛屼笉鏄痠<=n
for(int i=1; i<n; ++i)
cin >> t[1][i];
cout << "杈撳叆瑁呴厤綰?涓婄殑绔欏埌瑁呴厤綰?涓婄殑绔欐墍闇鏃墮棿t[2][j]: ";
for(int i=1; i<n; ++i)
cin >> t[2][i];
DP();
cout << "鏈蹇渶瑕佹椂闂? " << f << endl;
cout << "璺嚎鏄? " << endl;
PrintStation();
cout << endl;
}
]]>
絎崄鍥涚珷鎴戞兂鏀懼湪鍚庨潰鍐嶇湅錛屽厛鎼佷笅銆傚笇鏈涘ぇ瀹舵葷粨鐨勪竴浜涙枃绔犱篃鑳藉悜鎴戞帹鑽愪笅錛屽ぇ瀹朵簰鐩稿涔?fàn)銆?/p>
棣栧厛錛岃繕鏄緩璁湅鐪嬪墠璦錛?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
鍏舵錛岄樋闂紝鎰熻阿鑰佸ぉ閫佺粰浜?jiǎn)鎴戜滑杩欎箞涓鏈湥緇忥紝鐪嬩簡(jiǎn)榪欎竴绔狅紝鍐嶆鎰熷彈鍒頒簡(jiǎn)銆婄畻娉曞璁恒嬪垎鏋愰棶棰樼殑綺捐緹錛屽己鎮(zhèn)嶇殑欖呭姏銆侽rz, Orz,鍚勭Orz銆?/p>
榪欎竴绔犺鐨勬槸鍔ㄦ佽鍒掞紝瀛︾畻娉曠殑鏈嬪弸錛屽挨鍏舵槸鎼濧CM鐨勶紝瀵硅繖涓瓥鐣ヤ竴瀹氶潪甯哥啛鎮(zhèn)夛紝鎵浠ヨ繖涓畻娉曠綉涓婄殑鍒嗘瀽璁茶В鏁欑▼涔熸槸閾哄ぉ鐩栧湴錛屽ぇ瀹跺彲浠ュ鎼滃嚑綃囧涔?fàn)瀛︿範(fàn)銆?/p>
鍔ㄦ佽鍒?/strong>(Dynamic Programming錛岀畝縐癉P)鏄氳繃緇勫悎瀛愰棶棰樼殑瑙ｆ潵瑙ｅ喅闂鐨勩?/p>
娉ㄦ剰榪欓噷鐨刾rogramming涓嶆槸鎸囩紪紼嬶紝鑰屾槸鎸囦竴縐?strong>瑙勫垝
鍥犱負(fù)DP鐢ㄧ殑澶箍娉涗簡(jiǎn)錛屽茍涓斾功涓婁篃鑺變簡(jiǎn)寰堝ぇ鐨勭瘒騫呮潵璁茶繖涓绔狅紝鎵浠ユ垜涔熷噯澶囨妸榪欎竴绔犲垎鍑犵瘒鏉ユ葷粨錛屽茍涓旀垜涓嶆寜鐓т功涓婄殑欏哄簭鏉ユ葷粨錛屼篃涓嶄細(xì)鍏ㄩ儴鐢ㄤ功涓婄殑渚嬪瓙銆?/p>
榪欎竴绔犻鍏堢粰鍑轟竴浜涘熀紜鐨勬蹇碉紝鐒跺悗緇欏嚭涓涓渶鍩虹鍏ラ棬鐨凞P闂錛屼笁瑙掑艦姹傚奸棶棰樸?/p>
DP閫傜敤浜庡瓙闂?shù)笉鏄嫭绔嬬殑鎯呭喌锛寴q欐牱濡傛灉鐢ㄥ垎娌繪硶錛屼篃浼?xì)浣滆澶氶噸澶嶇殑宸ヤ綔锛岃孌P鍙瀛愰棶棰樻眰瑙ｄ竴嬈★紝灝嗗叾緇撴灉淇濆瓨鍦ㄤ竴寮犺〃涓紝浠庤岄伩鍏嶄簡(jiǎn)姣忔閬囧埌鍚勪釜瀛愰棶棰樻椂閲嶆柊璁＄畻鐨勬儏鍐點(diǎn)?/span>
姣旇緝鍒嗘不娉曚簬鍔ㄦ佽鍒掔殑鍖哄埆錛?/p>
鍒嗘不娉?/strong>錛氬皢闂鍒掑垎涓轟竴浜涚嫭绔嬬殑瀛愰棶棰橈紝閫掑綊鐨勬眰瑙ｅ悇瀛愰棶棰橈紝鐒跺悗鍚堝茍瀛愰棶棰樼殑瑙ｈ屽緱鍒板師闂鐨勮В銆?/p>
eg.MERGE-SORT(A, p, r)
1 if p < r
2 then q ← |(p + r)/2|
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)
鍔ㄦ佽鍒?/strong>錛?span style="color: rgb(0,0,255)">閫傜敤浜庡瓙闂涓嶆槸鐙珛鐨勬儏鍐碉紝涔熷氨鏄悇瀛愰棶棰樺寘鍚?strong>鍏叡鐨勫瓙瀛愰棶棰?/strong>錛岄壌浜庝細(xì)閲嶅鐨勬眰瑙ｅ悇瀛愰棶棰橈紝DP瀵規(guī)瘡涓棶
棰?strong>鍙眰瑙ｄ竴閬?/strong>錛屽皢鍏?strong>淇濆瓨鍦ㄤ竴寮犺〃涓紝浠庤岄伩鍏嶉噸澶嶈綆椼?/span>
DP綆楁硶鐨勮璁″彲浠ュ垎涓?strong>鍥涗釜姝ラ錛?/p>
①.鎻忚堪鏈浼樿В鐨勭粨鏋勩?/span>
②.閫掑綊瀹氫箟鏈浼樿В鐨勫箋?/span>
③.鎸夎嚜搴曡屼笂鐨勬柟寮忚綆楁渶浼樿В鐨勫箋?/span>
④.鐢辮綆楀嚭鐨勭粨鏋滃垱閫犱竴涓渶浼樿В銆?/span>
涓嬮潰鏉ョ湅鐪嬩笁瑙掑艦姹傚艱繖涓棶棰橈細(xì)
灝嗕竴涓敱N琛屾暟瀛楃粍鎴愮殑涓夎褰紝濡傚浘鎵浠ワ紝璁捐涓涓畻娉曪紝璁＄畻鍑轟笁瑙掑艦鐨勭敱欏惰嚦搴曠殑涓鏉¤礬寰勶紝浣胯璺緞緇忚繃鐨勬暟瀛楁誨拰鏈澶с?/p>
榪欐槸鍦ㄦ垜瑙佽繃鐨凞P棰樼洰涓紝綆楁槸鏈綆鍗曠殑浜?jiǎn)锛屾垜鐩镐俊灏苯帡娌℃湁瀛q嘍P鐨勪篃浼?xì)銆?/p>
灝嗕笂鍥捐漿鍖栦竴涓嬶細(xì)
鍋囪涓婂浘鐢╩ap[][]鏁扮粍淇濆瓨銆?/p>
浠[i][j]琛ㄧず浠庨《鐐?1, 1)鍒伴《鐐?i, j)鐨勬渶澶у箋?/p>
鍒欏彲浠ュ緱鍒扮姸鎬佽漿縐繪柟紼嬶細(xì)
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]
姝ら鏃㈤傚悎鑷《鑰屼笅鐨勬柟娉曞仛錛屼篃閫傚悎鑷簳鑰屼笂鐨勬柟娉曪紝
褰撶敤鑷《鑰屼笅鐨勬柟娉曞仛鏃訛紝鏈鍚庤鍦ㄥ湪鏈鍚庝竴鍒楁暟涓壘鍑烘渶澶у鹼紝
鑰岀敤鑷簳鑰屼笂鐨勬柟娉曞仛鏃訛紝f[1][1]鍗充負(fù)鏈澶у箋?/p>
鎵浠ユ垜浠皢鍥?鏍規(guī)嵁鐘舵佽漿縐繪柟紼嬪彲浠ュ緱鍒板浘3錛?/p>
鏈澶у兼槸30.
寰堢畝鍗曠殑DP棰橈紝浠ｇ爜濡備笅錛?/p>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/* Author: Tanky Woo Blog: www.WuTianQi.com Description: 鍔ㄦ佽鍒掍箣涓夎褰㈡眰鍊奸棶棰? */ #include <iostream> using namespace std; int map[6][6] = { {0, 0, 0, 0, 0, 0}, {0, 7, 0, 0, 0, 0}, {0, 3, 8, 0, 0, 0}, {0, 8, 1, 0, 0, 0}, {0, 2, 7, 4, 4, 0}, {0, 4, 5, 2, 6, 5} }; int f[6][6]; int _max(int a, int b) { if(a >= b) return a; return b; } int main() { memset(f, 0, sizeof(f)); for(int i=0; i<6; ++i) f[5][i] = map[5][i]; for(int i=4; i>=1; --i) for(int j=1; j<=i; ++j) f[i][j] = _max(f[i+1][j], f[i+1][j+1]) + map[i][j]; for(int i=1; i<=5; ++i) { for(int j=1; j<=5; ++j) { cout.width(2); cout << f[i][j] << " "; } cout << endl; } cout << f[1][1] << endl; } |
緇撴灉濡傚浘錛?/p>
涓嬩竴綃囦細(xì)灝嗚閰嶇嚎鐨勮皟搴︺?br />
鍦ㄦ垜鐙珛鍗氬涓婄殑鍘熸枃錛?a >http://www.wutianqi.com/?p=2484
嬈㈣繋澶у浜掔浉瀛︿範(fàn)錛屼簰鐩歌繘姝ワ紒
]]>
]]>
榪欎竴綃囨槸鍏充簬綰㈤粦鏍?wèi)鐨劸l撶偣鍒犻櫎銆?/p>
渚濈劧鍜屼笂涓綃囩殑鎻掑叆涓鏍鳳紝鍏堢敤鍒頒簡(jiǎn)BST鐨勫垹闄ょ粨鐐瑰嚱鏁幫紝鐒跺悗鍋氱浉搴旂殑璋冩暣銆?/p>
涓嶈繃錛岃繖閲岀殑璋冩暣鎬濊礬棰囦負(fù)鏂伴銆?/p>
榪樻槸鏉ョ湅鐪嬬暐寰敼鍙樺悗鐨勫垹闄ょ粨鐐瑰嚱鏁幫細(xì)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | Node* RBTreeDelete(RBTree T, Node *z) { Node *x, *y; // z鏄鍒犻櫎鐨勮妭鐐?鑰寉鏄鏇挎崲z鐨勮妭鐐?/span> if(z->lchild == NULL || z->rchild == NULL) y = z; // 褰撹鍒犻櫎鐨剒鑷沖鏈変竴涓瓙鏍?wèi)锛屽垯y=z錛?/span> else y = RBTreeSuccessor(z); // y鏄痾鐨勫悗緇?/span> if(y->lchild != NULL) x = y->lchild; else x = y->rchild; // 鏃犳潯浠舵墽琛宲[x] = p[y] x->parent = y->parent; if(y->parent == NULL) T = x; else if(y == y->parent->lchild) y->parent->lchild = x; else y->parent->rchild = x; if(y != z) z->key = y->key; if(y->color == BLACK) RBDeleteFixup(T, x); return y; } |
娉ㄦ剰浠ｇ爜鍊掓暟絎簩鍜岀涓夎錛屽彧鏈夊綋鍚庣戶緇撶偣y鐨勯鑹叉槸榛戣壊鏃訛紝鎵嶅仛璋冩暣銆?/p>
鐢辨錛屽紩瀵煎嚭鍑犱釜闂錛?/p>
1.闂細(xì)鑰冭檻涓轟綍褰搚鐨勯鑹叉槸榛戣壊鏃訛紝鎵嶈皟鏁達(dá)紵褰搚鐨勯鑹叉槸綰㈤粦鏃訛紝浼?xì)涓嶄細(xì)鐮村潖鎬ц川4錛?/span>
絳旓細(xì)榪欓噷鎴戜竴寮濮嬬籂緇撲簡(jiǎn)錛屽悗鏉ュ弽澶嶇湅浜?jiǎn)鍑爧啤BST鐨勫垹闄わ紝鍐嶇畻鎯抽氥傚湪BST涓紝鍒犻櫎緇撶偣z錛屽茍涓嶆槸鐪熺殑鎶妟緇欑Щ闄や簡(jiǎn)錛屽叾瀹炲垹闄ょ殑涓嶆槸z錛岃屾槸y錛佸洜涓簔濮嬬粓娌℃湁鍔ㄨ繃錛屽彧鏄妸y鍒犻櫎浜?jiǎn)锛岀劧鍚庢妸y鐨刱ey璧嬪肩粰z鐨刱ey銆傛墍浠ワ紝鍦ㄧ孩榛戞爲(wèi)涓紝z鐨勯鑹叉病鏈夊彉錛屼緷鐒剁鍚堢孩榛戞ц川銆傦紙榪欓噷鎴戝厛寮濮嬬悊瑙ｄ負(fù)y->color涔熻璧嬪肩粰z->color錛屾睏銆傘傘傦級(jí)
2.闂細(xì)鑰冭檻y涓洪粦鑹叉椂錛岀牬鍧忎簡(jiǎn)鍝嚑鏉＄孩榛戞ц川錛?/p>
絳旓細(xì)褰搚鏄牴鏃訛紝涓攜鐨勪竴涓瀛愭槸綰㈣壊錛岃嫢姝ゆ椂榪欎釜瀛╁瓙鎴愪負(fù)鏍圭粨鐐廣傗斺斺?gt;鐮村潖浜?jiǎn)鎬ц川2
褰搙鍜宲[y]閮芥槸綰㈣壊鏃躲?nbsp; 鈥斺斺?gt;鐮村潖浜?jiǎn)鎬ц川4
鍖呭惈y鐨勮礬寰勪腑錛岄粦楂樺害閮藉噺灝戜簡(jiǎn)銆?nbsp; 鈥斺斺?gt;鐮村潖浜?jiǎn)鎬ц川5
瑙ｅ喅鏂規(guī)硶錛?/p>
涓婁竴綃囨垜瑙ｉ噴榪囷紝鎬ц川浜旀秹鍙?qiáng)鍒颁簡(jiǎn)鏁磱倝|爲(wèi)錛岄毦浠ユ帶鍒躲?/p>
鍥犳灝唜鐨勯鑹插鍔犱竴閲嶉粦鑹詫紝閭ｄ箞褰?
鈶?x鍘熷厛棰滆壊涓篟ED鏃垛斺?>x鍖呭惈RED鍜孊LACK涓ら鑹?/span>
鈶?x鍘熷厛棰滆壊鏄疊LACK鏃垛?#8211;>x鍖呭惈BLACK, BLACK涓ら鑹層?/span>
姝ゆ椂鎬ц川5瑙ｅ喅錛屼絾鏄張鐮村潖浜?jiǎn)鎬ц川1.
鎺ヤ笅鏉ュ氨鏄仮澶嶆ц川1錛?錛?浜?jiǎn)銆?/p>
灝嗛澶栫殑涓閲嶉粦鑹蹭竴鐩存部鏍?wèi)鍚戜笂绉诲Q岀洿鍒皒鏄牴鎴栬呮槸綰㈣壊緇撶偣銆?/span>
鐪嬬湅鍏蜂綋鐨勫疄鐜頒唬鐮侊細(xì)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | void RBDeleteFixup(RBTree &T, Node *x) { while(x != T && x->color == BLACK) { if(x == x->parent->lchild) { Node *w = x->parent->rchild; ///////////// Case 1 ///////////// if(w->color == RED) { w->color = BLACK; x->parent->color = RED; LeftRotate(T, x->parent); w = x->parent->rchild; } ///////////// Case 2 ///////////// if(w->lchild->color == BLACK && w->rchild->color == BLACK) { w->color = RED; x = x->parent; } else { ///////////// Case 3 ///////////// if(w->rchild->color == BLACK) { w->lchild->color = BLACK; w->color = RED; RightRotate(T, w); w = x->parent->rchild; } ///////////// Case 4 ///////////// w->color = x->parent->color; x->parent->color = BLACK; w->rchild->color = BLACK; LeftRotate(T, x->parent); x = T; } } else { Node *w = x->parent->lchild; if(w->color == RED) { w->color = BLACK; x->parent->color = RED; RightRotate(T, x->parent); w = x->parent->lchild; } if(w->lchild->color == BLACK && w->rchild->color == BLACK) { w->color = RED; x = x->parent; } else { if(w->lchild->color == BLACK) { w->rchild->color = BLACK; w->color = RED; LeftRotate(T, w); w = x->parent->lchild; } w->color = x->parent->color; x->parent->color = BLACK; w->lchild->color = BLACK; RightRotate(T, x->parent); x = T; } } } x->color = BLACK; } |
瀵逛簬鍒犻櫎鐨勮皟鏁達(dá)紝鍏卞叓縐嶆儏鍐?宸﹀彸瀵圭О鍚勫洓縐?錛岃繖閲屽湪涔︿笂P175闈㈣鐨勫緢璇︾粏錛屾墍浠ユ垜涔熷氨涓嶅啀鐢誨浘浜?jiǎn)锛屽ぇ瀹跺彲浠ヨ嚜宸辨嬁钃v絎斿湪鑽夌ǹ綰鎬笂鐢諱竴
鍦ㄦ垜鐙珛鍗氬涓婄殑鍘熸枃錛歨ttp://www.wutianqi.com/?p=2449
嬈㈣繋澶у浜掔浉璁ㄨ錛屼竴璧瘋繘姝ワ紒
]]>
寤鴻鍏堢湅鐪嬪墠璦錛?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
鎻掑叆緇撶偣鐢ㄥ埌浜?jiǎn)涓婁竴嬈ST鐨勬彃鍏ュ嚱鏁?鍋氫簡(jiǎn)涓鐐規(guī)坊鍔?錛屽茍涓斿湪姝ゅ熀紜涓婂鍔犱簡(jiǎn)淇濇寔綰㈤粦鎬ц川鐨勮皟鏁村嚱鏁般?/p>
榪樻槸鍏堢湅鐪嬫彃鍏ュ嚱鏁幫細(xì)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
void RBTreeInsert(RBTree &T, int k) { //T->parent->color = BLACK; Node *y = NULL; Node *x = T; Node *z = new Node; z->key = k; z->lchild = z->parent = z->rchild = NULL; while(x != NULL) { y = x; if(k < x->key) x = x->lchild; else x = x->rchild; } z->parent = y; if(y == NULL) { T = z; T->parent = NULL; T->parent->color = BLACK; } else if(k < y->key) y->lchild = z; else y->rchild = z; z->lchild = NULL; z->rchild = NULL; z->color = RED; RBInsertFixup(T, z); } |
鍜屼笂涓嬈＄殑BST鍩烘湰娌″尯鍒紝鍙槸娣誨姞浜?jiǎn)瀵规柊鍔牼l撶偣z鐨勯鑹插拰瀛愯妭鐐圭殑澶勭悊銆?/p>
榪欓噷鎶妟鐨勯鑹茶緗負(fù)綰㈣壊錛岀劧鍚庤繘琛屽鐞嗐?/p>
闂?/strong>錛氳冭檻涓轟綍鎶妟鐨勯鑹茶緗負(fù)綰㈣壊錛?/p>
絳?/strong>錛氫釜浜鴻涓哄鏋滆緗負(fù)榛戣壊錛屽垯鐮村潖浜?jiǎn)鎬ц川浜旓紝鑰屾ц川浜斿叧浜庨粦楂樺害鐨勯棶棰橈紝娑夊強(qiáng)鍒頒簡(jiǎn)鏁存５鏍?wèi)锛屽叏灞鎬ч毦浠ユ妸鎻★紝鎵浠ヨ繖閲岃緗負(fù)綰㈣壊錛岃櫧鐒剁牬鍧忎簡(jiǎn)鎬ц川4錛岀劧鏄浉瀵圭牬鍧忔ц川5鏉ヨ錛屾洿瀹規(guī)槗鎭㈠綰㈤粦鎬ц川銆傚ぇ瀹跺鏋滄湁涓嶅悓鐨勬兂娉曪紝涔熷彲浠ョ暀璦璋堣皥銆?/span>
鎺ヤ笅鏉ワ紝灝辨槸瀵規(guī)暣媯墊爲(wèi)鐨勮皟鏁翠簡(jiǎn)銆?/p>
絳旓細(xì)鑰冭檻鎻掑叆z緇撶偣鍚庯紝鐮村潖鐨勫摢鍑犳潯綰㈤粦鎬ц川錛?/p>
絳旓細(xì)鐮村潖浜?jiǎn)鎬ц川2鍜屾ц川4.
5鏉＄孩榛戞ц川瑕佺啛璁幫紝鎴戣繖閲屽啀璐村嚭鏉ワ細(xì)
1. 姣忎釜緇撶偣鎴栨槸綰㈣壊錛屾垨鏄槸榛戣壊銆?br>2. 鏍圭粨鐐規(guī)槸榛戠殑銆?br>3. 鎵鏈夌殑鍙剁粨鐐?NULL)鏄粦鑹茬殑銆傦紙NULL琚涓轟竴涓摠鍏電粨鐐癸紝鎵鏈夊簲璇ユ寚鍚慛ULL鐨勬寚閽堬紝閮界湅鎴愭寚鍚戜簡(jiǎn)NULL緇撶偣銆傦級(jí)
4. 濡傛灉涓涓粨鐐規(guī)槸綰㈣壊鐨勶紝鍒欏畠鐨勪袱涓効瀛愯妭鐐歸兘鏄粦鑹茬殑銆?br>5. 瀵規(guī)瘡涓粨鐐癸紝浠庤緇撶偣鍒板叾瀛愬瓩緇撶偣鐨勬墍鏈夎礬寰勪笂鍖呭惈鐩稿悓鏁扮洰鐨勯粦緇撶偣銆?/p>
鎵浠ユ垜浠鍋氱殑灝辨槸鎭㈠鎬ц川2鍜屾ц川4.
鍏堟潵鐪嬬湅鍏蜂綋瀹炵幇鐨勪唬鐮?榪欓噷鍙創(chuàng)鍑洪儴鍒嗕唬鐮?錛?/p>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
void RBInsertFixup(RBTree &T, Node *z) { while(z->parent->color == RED) { if(z->parent == z->parent->parent->lchild) { Node *y = z->parent->parent->rchild; //////////// Case1 ////////////// if(y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { ////////////// Case 2 ////////////// if(z == z->parent->rchild) { z = z->parent; LeftRotate(T, z); } ////////////// Case 3 ////////////// z->parent->color = BLACK; z->parent->parent->color = RED; RightRotate(T, z->parent->parent); } } else { /////////////////////// } } T->color = BLACK; } |
鍒嗕笁縐嶆儏鍐碉紝鍦ㄤ唬鐮佷腑宸茬敤Case 1, Case 2, Case 3鏍囪鍑恒?/p>
澶ц嚧璇翠笅鍒ゆ柇鎯呭喌錛?/p>
1.棣栧厛璁╀竴涓寚閽坹鎸囧悜z鐨?span style="COLOR: rgb(0,0,255)">鍙旂埗緇撶偣
(z鏄鍒犻櫎鐨勭粨鐐?銆?/p>2.濡傛灉y(cè)鐨勯鑹叉槸綰㈣壊錛孋ase 1銆傚垯浣縵鐨勭埗浜茬粨鐐瑰拰鍙旂埗緇撶偣鐨勯鑹叉敼涓洪粦錛寊鐨勭鐖剁粨鐐歸鑹叉敼涓虹孩銆傜劧鍚庤z杞Щ鍒皕鐨勭鐖剁粨鐐廣?/p>
3.褰搚鐨勯鑹叉槸榛戣壊鏃訛紝
鈶?棣栧厛鍒ゆ柇z鏄惁鏄叾鐖朵翰緇撶偣鐨勫彸鍎垮瓙錛岃嫢鏄紝鍒?span style="COLOR: rgb(0,0,255)">璋冩暣涓哄乏鍎垮瓙(鐢ㄦ棆杞?銆?/p>
鈶?鍏舵浣縵鐨勭埗浜茬粨鐐歸鑹蹭負(fù)榛戯紝z鐨勭鐖剁粨鐐歸鑹蹭負(fù)綰紝騫朵互z鐨勭鐖剁粨鐐?/span>涓鴻醬鍙蟲(chóng)棆銆?/p>
鍏蜂綋鎴戣繕鏄湪鑽夌ǹ綰鎬笂鐢誨嚭銆傘傘?鍙滀拱涓嶈搗鏁扮爜鐩告満錛屽彧鑳界敤鎵嬫満鎷嶄簡(jiǎn)銆傘傘? 錛堝急寮辯殑闂竴鍙ワ紝鐪嬭緗戜笂鏈夊緢澶氭湅鍙嬪仛鐨勪竴浜涗唬鐮佽瑙ｅ浘寰堢粰鍔涳紝涓嶇煡閬撳ぇ瀹舵湁浠涔堣蔣浠跺悧錛熸眰鎺ㄨ崘銆傘傘傦級(jí) 浠ヤ笅鏄彃鍏ョ殑瀹屾暣浠ｇ爜錛?/p>
涓嬩竴綃囨槸鍏充簬綰㈤粦鏍?wèi)鐨勫垹闄ゃ?br>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
void RBInsertFixup(RBTree &T, Node *z)
{
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->lchild)
{
Node *y = z->parent->parent->rchild;
//////////// Case1 //////////////
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
////////////// Case 2 //////////////
if(z == z->parent->rchild)
{
z = z->parent;
LeftRotate(T, z);
}
////////////// Case 3 //////////////
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else
{
Node *y = z->parent->parent->lchild;
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->lchild)
{
z = z->parent;
RightRotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
LeftRotate(T, z->parent->parent);
}
}
}
T->color = BLACK;
}
void RBTreeInsert(RBTree &T, int k)
{
//T->parent->color = BLACK;
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
T->parent = NULL;
T->parent->color = BLACK;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
z->color = RED;
RBInsertFixup(T, z);
}
]]>