鑳屽寘闂涔?jié)璁?br>version 1.1 build 20071115
鍓嶈█
鐩綍
絎竴璁?01鑳屽寘闂
絎簩璁?瀹屽叏鑳屽寘闂
絎笁璁?澶氶噸鑳屽寘闂
絎洓璁?娣峰悎涓夌鑳屽寘闂
絎簲璁?浜岀淮璐圭敤鐨勮儗鍖呴棶棰?
絎叚璁?鍒嗙粍鐨勮儗鍖呴棶棰?
絎竷璁?鏈変緷璧栫殑鑳屽寘闂
絎叓璁?娉涘寲鐗╁搧
絎節(jié)璁?鑳屽寘闂闂硶鐨勫彉鍖?
闄勫綍涓錛歎SACO涓殑鑳屽寘闂
闄勫綍浜岋細(xì)鑳屽寘闂鐨勬悳绱㈣В娉?
鑱旂郴鏂瑰紡
鑷磋阿
鍓嶈█
鏈瘒鏂囩珷鏄垜(dd_engi)姝ｅ湪榪涜涓殑涓涓泟蹇冨媰鍕冪殑鍐欎綔璁″垝鐨勪竴閮ㄥ垎錛岃繖涓鍒掔殑鍐呭鏄啓浣滀竴浠借緝涓哄畬鍠勭殑NOIP闅懼害鐨勫姩鎬佽鍒掓葷粨錛屽悕涓恒婅В鍔ㄦ佽鍒掗鐨勫熀鏈濊冩柟寮忋嬨傜幇鍦ㄤ綘鐪嬪埌鐨勬槸榪欎釜鍐欎綔璁″垝鏈鍏堝彂甯冪殑涓閮ㄥ垎銆?/p>
鑳屽寘闂鏄竴涓粡鍏哥殑鍔ㄦ佽鍒掓ā鍨嬨傚畠鏃㈢畝鍗曞艦璞″鏄撶悊瑙ｏ紝鍙堝湪鏌愮紼嬪害涓婅兘澶熸彮紺哄姩鎬佽鍒掔殑鏈川錛屾晠涓嶅皯鏁欐潗閮芥妸瀹冧綔涓哄姩鎬佽鍒掗儴鍒嗙殑絎竴閬撲緥棰橈紝鎴戜篃灝嗗畠鏀懼湪鎴戠殑鍐欎綔璁″垝鐨勭涓閮ㄥ垎銆?/p>
璇繪湰鏂囨渶閲嶈鐨勬槸鎬濊冦傚洜涓烘垜鐨勮璦鍜屽啓浣滄柟寮忓悜鏉ヤ笉浠ユ槗浜庣悊瑙ｄ負(fù)闀匡紝鎬濊礬涔熷伓鏈夎煩璺冪殑鍦版柟錛屽悗闈㈡洿鏈夐渶瑕佸ぇ閲忔濊冩墠鑳界悊瑙ｇ殑姣旇緝鎶借薄鐨勫唴瀹廣傛洿閲嶈鐨勬槸錛氫笉澶ч噺鎬濊冿紝緇濆涓嶅彲鑳藉濂藉姩鎬佽鍒掕繖涓淇℃伅瀛﹀ゥ璧涗腑鏈綺捐嚧鐨勯儴鍒嗐?/p>
浣犵幇鍦ㄧ湅鍒扮殑鏄湰鏂囩殑v1.1鐗堬紝鍙戝竷浜?007騫?1鏈?5鏃ャ傛垜浼?xì)闀挎湡缁存姢杩欎唤鏂囨湰锛屾妸澶у鐨勬剰瑙佸拰寰忚铻嶅叆鍏朵腑锛屼篃浼?xì)涓嶆柇鍔犲叆鎴戝湪OI瀛︿範(fàn)浠ュ強(qiáng)灝嗘潵鍙兘鐨凙CM-ICPC鐨勫緛紼嬩腑寰楀埌鐨勬柊鐨勫績寰椼備絾鐩墠鏈枃榪樻病鏈変竴涓浐瀹氱殑鍙戝竷欏甸潰錛屾兂浜嗚В鏈枃鏄惁鏈夋洿鏂扮増鏈彂甯冿紝鍙互鍦∣IBH璁哄潧涓互“鑳屽寘闂涔?jié)璁?#8221;涓哄叧閿瓧鎼滅儲璐村瓙錛屾瘡嬈℃瘮杈冮噸澶х殑鐗堟湰鏇存柊閮戒細(xì)鍦ㄨ繖涓鍧涢噷鍙戣創(chuàng)鍏竷銆備篃鍙互鐢?#8220;鑳屽寘闂涔?jié)璁?#8221;涓哄叧閿瓧鍦ㄦ悳绱㈠紩鎿庝腑鎼滅儲浠ュ緱鍒版渶鏂扮増鏈?/p>
鐩綍
絎竴璁?01鑳屽寘闂
榪欐槸鏈鍩烘湰鐨勮儗鍖呴棶棰橈紝姣忎釜鐗╁搧鏈澶氬彧鑳芥斁涓嬈°?/p>
P01: 01鑳屽寘闂
棰樼洰
鏈塏浠剁墿鍝佸拰涓涓閲忎負(fù)V鐨勮儗鍖呫傜i浠剁墿鍝佺殑璐圭敤鏄痗[i]錛屼環(huán)鍊兼槸w[i]銆傛眰瑙ｅ皢鍝簺鐗╁搧瑁呭叆鑳屽寘鍙嬌浠峰兼誨拰鏈澶с?/p>
鍩烘湰鎬濊礬
榪欐槸鏈鍩虹鐨勮儗鍖呴棶棰橈紝鐗圭偣鏄細(xì)姣忕鐗╁搧浠呮湁涓浠訛紝鍙互閫夋嫨鏀炬垨涓嶆斁銆?/p>
鐢ㄥ瓙闂瀹氫箟鐘舵侊細(xì)鍗砯[i][v]琛ㄧず鍓峣浠剁墿鍝佹伆鏀懼叆涓涓閲忎負(fù)v鐨勮儗鍖呭彲浠ヨ幏寰楃殑鏈澶т環(huán)鍊箋傚垯鍏剁姸鎬佽漿縐繪柟紼嬩究鏄細(xì)
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
榪欎釜鏂圭▼闈炲父閲嶈錛屽熀鏈笂鎵鏈夎窡鑳屽寘鐩稿叧鐨勯棶棰樼殑鏂圭▼閮芥槸鐢卞畠琛嶇敓鍑烘潵鐨勩傛墍浠ユ湁蹇呰灝嗗畠璇︾粏瑙ｉ噴涓涓嬶細(xì)“灝嗗墠i浠剁墿鍝佹斁鍏ュ閲忎負(fù)v鐨勮儗鍖呬腑”榪欎釜瀛愰棶棰橈紝鑻ュ彧鑰冭檻絎琲浠剁墿鍝佺殑絳栫暐錛堟斁鎴栦笉鏀撅級錛岄偅涔堝氨鍙互杞寲涓轟竴涓彧鐗墊壇鍓峣-1浠剁墿鍝佺殑闂銆傚鏋滀笉鏀劇i浠剁墿鍝侊紝閭ｄ箞闂灝辮漿鍖栦負(fù)“鍓峣-1浠剁墿鍝佹斁鍏ュ閲忎負(fù)v鐨勮儗鍖呬腑”錛屼環(huán)鍊間負(fù)f[i-1][v]錛涘鏋滄斁絎琲浠剁墿鍝侊紝閭ｄ箞闂灝辮漿鍖栦負(fù)“鍓峣-1浠剁墿鍝佹斁鍏ュ墿涓嬬殑瀹歸噺涓簐-c[i]鐨勮儗鍖呬腑”錛屾鏃惰兘鑾峰緱鐨勬渶澶т環(huán)鍊煎氨鏄痜[i-1][v-c[i]]鍐嶅姞涓婇氳繃鏀懼叆絎琲浠剁墿鍝佽幏寰楃殑浠峰紈[i]銆?/p>
浼樺寲絀洪棿澶嶆潅搴?br>浠ヤ笂鏂規(guī)硶鐨勬椂闂村拰絀洪棿澶嶆潅搴﹀潎涓篛(VN)錛屽叾涓椂闂村鏉傚害搴旇宸茬粡涓嶈兘鍐嶄紭鍖栦簡錛屼絾絀洪棿澶嶆潅搴﹀嵈鍙互浼樺寲鍒癘銆?/p>
鍏堣冭檻涓婇潰璁茬殑鍩烘湰鎬濊礬濡備綍瀹炵幇錛岃偗瀹氭槸鏈変竴涓富寰幆i=1..N錛屾瘡嬈＄畻鍑烘潵浜岀淮鏁扮粍f[i][0..V]鐨勬墍鏈夊箋傞偅涔堬紝濡傛灉鍙敤涓涓暟緇刦[0..V]錛岃兘涓嶈兘淇濊瘉絎琲嬈″驚鐜粨鏉熷悗f[v]涓〃紺虹殑灝辨槸鎴戜滑瀹氫箟鐨勭姸鎬乫[i][v]鍛紵f[i][v]鏄敱f[i-1][v]鍜宖[i-1][v-c[i]]涓や釜瀛愰棶棰橀掓帹鑰屾潵錛岃兘鍚︿繚璇佸湪鎺╢[i][v]鏃訛紙涔熷嵆鍦ㄧi嬈′富寰幆涓帹f[v]鏃訛級鑳藉寰楀埌f[i-1][v]鍜宖[i-1][v-c[i]]鐨勫煎憿錛熶簨瀹炰笂錛岃繖瑕佹眰鍦ㄦ瘡嬈′富寰幆涓垜浠互v=V..0鐨勯『搴忔帹f[v]錛岃繖鏍鋒墠鑳戒繚璇佹帹f[v]鏃秄[v-c[i]]淇濆瓨鐨勬槸鐘舵乫[i-1][v-c[i]]鐨勫箋備吉浠ｇ爜濡備笅錛?/p>
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
鍏朵腑鐨刦[v]=max{f[v],f[v-c[i]]}涓鍙ユ伆灝辯浉褰撲簬鎴戜滑鐨勮漿縐繪柟紼媐[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}錛屽洜涓虹幇鍦ㄧ殑f[v-c[i]]灝辯浉褰撲簬鍘熸潵鐨刦[i-1][v-c[i]]銆傚鏋滃皢v鐨勫驚鐜『搴忎粠涓婇潰鐨勯嗗簭鏀規(guī)垚欏哄簭鐨勮瘽錛岄偅涔堝垯鎴愪簡f[i][v]鐢眆[i][v-c[i]]鎺ㄧ煡錛屼笌鏈鎰忎笉絎︼紝浣嗗畠鍗存槸鍙︿竴涓噸瑕佺殑鑳屽寘闂P02鏈綆鎹風(fēng)殑瑙ｅ喅鏂規(guī)錛屾晠瀛︿範(fàn)鍙敤涓緇存暟緇勮В01鑳屽寘闂鏄崄鍒嗗繀瑕佺殑銆?/p>
浜嬪疄涓婏紝浣跨敤涓緇存暟緇勮В01鑳屽寘鐨勭▼搴忓湪鍚庨潰浼?xì)琚娆＄敤鍒板Q屾墍浠ヨ繖閲屾娊璞″嚭涓涓鐞嗕竴浠?1鑳屽寘涓殑鐗╁搧榪囩▼錛屼互鍚庣殑浠ｇ爜涓洿鎺ヨ皟鐢ㄤ笉鍔犺鏄庛?/p>
榪囩▼ZeroOnePack錛岃〃紺哄鐞嗕竴浠?1鑳屽寘涓殑鐗╁搧錛屼袱涓弬鏁癱ost銆亀eight鍒嗗埆琛ㄦ槑榪欎歡鐗╁搧鐨勮垂鐢ㄥ拰浠峰箋?/p>
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
娉ㄦ剰榪欎釜榪囩▼閲岀殑澶勭悊涓庡墠闈㈢粰鍑虹殑浼唬鐮佹湁鎵涓嶅悓銆傚墠闈㈢殑紺轟緥紼嬪簭鍐欐垚v=V..0鏄負(fù)浜嗗湪紼嬪簭涓綋鐜版瘡涓姸鎬侀兘鎸夌収鏂圭▼姹傝В浜嗭紝閬垮厤涓嶅繀瑕佺殑鎬濈淮澶嶆潅搴︺傝岃繖閲屾棦鐒跺凡緇忔娊璞℃垚鐪嬩綔榛戠鐨勮繃紼嬩簡錛屽氨鍙互鍔犲叆浼樺寲銆傝垂鐢ㄤ負(fù)cost鐨勭墿鍝佷笉浼?xì)濯?jiǎng)鍝嶇姸鎬乫[0..cost-1]錛岃繖鏄樉鐒剁殑銆?/p>
鏈変簡榪欎釜榪囩▼浠ュ悗錛?1鑳屽寘闂鐨勪吉浠ｇ爜灝卞彲浠ヨ繖鏍峰啓錛?/p>
for i=1..N
ZeroOnePack(c[i],w[i]);
鍒濆鍖栫殑緇嗚妭闂
鎴戜滑鐪嬪埌鐨勬眰鏈浼樿В鐨勮儗鍖呴棶棰橀鐩腑錛屼簨瀹炰笂鏈変袱縐嶄笉澶浉鍚岀殑闂硶銆傛湁鐨勯鐩姹?#8220;鎭板ソ瑁呮弧鑳屽寘”鏃剁殑鏈浼樿В錛屾湁鐨勯鐩垯騫舵病鏈夎姹傚繀欏繪妸鑳屽寘瑁呮弧銆備竴縐嶅尯鍒繖涓ょ闂硶鐨勫疄鐜版柟娉曟槸鍦ㄥ垵濮嬪寲鐨勬椂鍊欐湁鎵涓嶅悓銆?/p>
濡傛灉鏄涓縐嶉棶娉曪紝瑕佹眰鎭板ソ瑁呮弧鑳屽寘錛岄偅涔堝湪鍒濆鍖栨椂闄や簡f[0]涓?鍏跺畠f[1..V]鍧囪涓?∞錛岃繖鏍峰氨鍙互淇濊瘉鏈緇堝緱鍒扮殑f[N]鏄竴縐嶆伆濂借婊¤儗鍖呯殑鏈浼樿В銆?/p>
濡傛灉騫舵病鏈夎姹傚繀欏繪妸鑳屽寘瑁呮弧錛岃屾槸鍙笇鏈涗環(huán)鏍煎敖閲忓ぇ錛屽垵濮嬪寲鏃跺簲璇ュ皢f[0..V]鍏ㄩ儴璁句負(fù)0銆?/p>
涓轟粈涔堝憿錛熷彲浠ヨ繖鏍風(fēng)悊瑙ｏ細(xì)鍒濆鍖栫殑f鏁扮粍浜嬪疄涓婂氨鏄湪娌℃湁浠諱綍鐗╁搧鍙互鏀懼叆鑳屽寘鏃剁殑鍚堟硶鐘舵併傚鏋滆姹傝儗鍖呮伆濂借婊★紝閭ｄ箞姝ゆ椂鍙湁瀹歸噺涓?鐨勮儗鍖呭彲鑳借浠峰間負(fù)0鐨刵othing“鎭板ソ瑁呮弧”錛屽叾瀹冨閲忕殑鑳屽寘鍧囨病鏈夊悎娉曠殑瑙ｏ紝灞炰簬鏈畾涔夌殑鐘舵侊紝瀹冧滑鐨勫煎氨閮藉簲璇ユ槸-∞浜嗐傚鏋滆儗鍖呭茍闈炲繀欏昏瑁呮弧錛岄偅涔堜換浣曞閲忕殑鑳屽寘閮芥湁涓涓悎娉曡В“浠涔堥兘涓嶈”錛岃繖涓В鐨勪環(huán)鍊間負(fù)0錛屾墍浠ュ垵濮嬫椂鐘舵佺殑鍊間篃灝卞叏閮ㄤ負(fù)0浜嗐?/p>
榪欎釜灝忔妧宸у畬鍏ㄥ彲浠ユ帹騫垮埌鍏跺畠綾誨瀷鐨勮儗鍖呴棶棰橈紝鍚庨潰涔熷氨涓嶅啀瀵硅繘琛岀姸鎬佽漿縐諱箣鍓嶇殑鍒濆鍖栬繘琛岃瑙ｃ?/p>
涓涓父鏁頒紭鍖?br>鍓嶉潰鐨勪吉浠ｇ爜涓湁 for v=V..1錛屽彲浠ュ皢榪欎釜寰幆鐨勪笅闄愯繘琛屾敼榪涖?/p>
鐢變簬鍙渶瑕佹渶鍚巉[v]鐨勫鹼紝鍊掓帹鍓嶄竴涓墿鍝侊紝鍏跺疄鍙鐭ラ亾f[v-w[n]]鍗沖彲銆備互姝ょ被鎺紝瀵逛互絎琷涓儗鍖咃紝鍏跺疄鍙渶瑕佺煡閬撳埌f[v-sum{w[j..n]}]鍗沖彲錛屽嵆浠ｇ爜涓殑
for i=1..N
for v=V..0
鍙互鏀規(guī)垚
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
榪欏浜嶸姣旇緝澶ф椂鏄湁鐢ㄧ殑銆?/p>
灝忕粨
01鑳屽寘闂鏄渶鍩烘湰鐨勮儗鍖呴棶棰橈紝瀹冨寘鍚簡鑳屽寘闂涓璁＄姸鎬併佹柟紼嬬殑鏈鍩烘湰鎬濇兂錛屽彟澶栵紝鍒殑綾誨瀷鐨勮儗鍖呴棶棰樺線寰涔熷彲浠ヨ漿鎹㈡垚01鑳屽寘闂姹傝В銆傛晠涓瀹氳浠旂粏浣撲細(xì)涓婇潰鍩烘湰鎬濊礬鐨勫緱鍑烘柟娉曪紝鐘舵佽漿縐繪柟紼嬬殑鎰忎箟錛屼互鍙?qiáng)鏈鍚庢庢牱浼樺寲鐨勭┖闂村鏉傚害銆?br>
絎簩璁?瀹屽叏鑳屽寘闂
絎簩涓熀鏈殑鑳屽寘闂妯″瀷錛屾瘡縐嶇墿鍝佸彲浠ユ斁鏃犻檺澶氭銆?br>P02: 瀹屽叏鑳屽寘闂
棰樼洰
鏈塏縐嶇墿鍝佸拰涓涓閲忎負(fù)V鐨勮儗鍖咃紝姣忕鐗╁搧閮芥湁鏃犻檺浠跺彲鐢ㄣ傜i縐嶇墿鍝佺殑璐圭敤鏄痗[i]錛屼環(huán)鍊兼槸w[i]銆傛眰瑙ｅ皢鍝簺鐗╁搧瑁呭叆鑳屽寘鍙嬌榪欎簺鐗╁搧鐨勮垂鐢ㄦ誨拰涓嶈秴榪囪儗鍖呭閲忥紝涓斾環(huán)鍊兼誨拰鏈澶с?/p>
鍩烘湰鎬濊礬
榪欎釜闂闈炲父綾諱技浜?1鑳屽寘闂錛屾墍涓嶅悓鐨勬槸姣忕鐗╁搧鏈夋棤闄愪歡銆備篃灝辨槸浠庢瘡縐嶇墿鍝佺殑瑙掑害鑰冭檻錛屼笌瀹冪浉鍏崇殑絳栫暐宸插茍闈炲彇鎴栦笉鍙栦袱縐嶏紝鑰屾槸鏈夊彇0浠躲佸彇1浠躲佸彇2浠?#8230;…絳夊緢澶氱銆傚鏋滀粛鐒舵寜鐓цВ01鑳屽寘鏃剁殑鎬濊礬錛屼護(hù)f[i][v]琛ㄧず鍓峣縐嶇墿鍝佹伆鏀懼叆涓涓閲忎負(fù)v鐨勮儗鍖呯殑鏈澶ф潈鍊箋備粛鐒跺彲浠ユ寜鐓ф瘡縐嶇墿鍝佷笉鍚岀殑絳栫暐鍐欏嚭鐘舵佽漿縐繪柟紼嬶紝鍍忚繖鏍鳳細(xì)
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
榪欒窡01鑳屽寘闂涓鏍鋒湁O(VN)涓姸鎬侀渶瑕佹眰瑙ｏ紝浣嗘眰瑙ｆ瘡涓姸鎬佺殑鏃墮棿宸茬粡涓嶆槸甯告暟浜嗭紝姹傝В鐘舵乫[i][v]鐨勬椂闂存槸O(v/c[i])錛屾葷殑澶嶆潅搴﹀彲浠ヨ涓烘槸O(V*Σ(V/c[i]))錛屾槸姣旇緝澶х殑銆?/p>
灝?1鑳屽寘闂鐨勫熀鏈濊礬鍔犱互鏀硅繘錛屽緱鍒頒簡榪欐牱涓涓竻鏅扮殑鏂規(guī)硶銆傝繖璇存槑01鑳屽寘闂鐨勬柟紼嬬殑紜槸寰堥噸瑕侊紝鍙互鎺ㄥ強(qiáng)鍏跺畠綾誨瀷鐨勮儗鍖呴棶棰樸備絾鎴戜滑榪樻槸璇曞浘鏀硅繘榪欎釜澶嶆潅搴︺?/p>
涓涓畝鍗曟湁鏁堢殑浼樺寲
瀹屽叏鑳屽寘闂鏈変竴涓緢綆鍗曟湁鏁堢殑浼樺寲錛屾槸榪欐牱鐨勶細(xì)鑻ヤ袱浠剁墿鍝乮銆乯婊¤凍c[i]<=c[j]涓攚[i]>=w[j]錛屽垯灝嗙墿鍝乯鍘繪帀錛屼笉鐢ㄨ冭檻銆傝繖涓紭鍖栫殑姝ｇ‘鎬ф樉鐒?dòng)灱?xì)浠諱綍鎯呭喌涓嬮兘鍙皢浠峰煎皬璐圭敤楂樺緱j鎹㈡垚鐗╃編浠峰粔鐨刬錛屽緱鍒拌嚦灝戜笉浼?xì)鏇村樊鐨勬栆?guī)銆傚浜庨殢鏈虹敓鎴愮殑鏁版嵁錛岃繖涓柟娉曞線寰浼?xì)澶уぇ鍑彏畱鐗╁搧鐨勪欢鏁板Q屼粠鑰屽姞蹇熷害銆傜劧鑰岃繖涓茍涓嶈兘鏀瑰杽鏈鍧忔儏鍐電殑澶嶆潅搴︼紝鍥犱負(fù)鏈夊彲鑳界壒鍒璁＄殑鏁版嵁鍙互涓浠剁墿鍝佷篃鍘諱笉鎺夈?/p>
榪欎釜浼樺寲鍙互綆鍗曠殑O(N^2)鍦板疄鐜幫紝涓鑸兘鍙互鎵垮彈銆傚彟澶栵紝閽堝鑳屽寘闂鑰岃█錛屾瘮杈冧笉閿欑殑涓縐嶆柟娉曟槸錛氶鍏堝皢璐圭敤澶т簬V鐨勭墿鍝佸幓鎺夛紝鐒跺悗浣跨敤綾諱技璁℃暟鎺掑簭鐨勫仛娉曪紝璁＄畻鍑鴻垂鐢ㄧ浉鍚岀殑鐗╁搧涓環(huán)鍊兼渶楂樼殑鏄摢涓紝鍙互O(V+N)鍦板畬鎴愯繖涓紭鍖栥傝繖涓笉澶噸瑕佺殑榪囩▼灝變笉緇欏嚭浼唬鐮佷簡錛屽笇鏈涗綘鑳界嫭绔嬫濊冨啓鍑轟吉浠ｇ爜鎴栫▼搴忋?/p>
杞寲涓?1鑳屽寘闂姹傝В
鏃㈢劧01鑳屽寘闂鏄渶鍩烘湰鐨勮儗鍖呴棶棰橈紝閭ｄ箞鎴戜滑鍙互鑰冭檻鎶婂畬鍏ㄨ儗鍖呴棶棰樿漿鍖栦負(fù)01鑳屽寘闂鏉ヨВ銆傛渶綆鍗曠殑鎯蟲硶鏄紝鑰冭檻鍒扮i縐嶇墿鍝佹渶澶氶塚/c[i]浠訛紝浜庢槸鍙互鎶婄i縐嶇墿鍝佽漿鍖栦負(fù)V/c[i]浠惰垂鐢ㄥ強(qiáng)浠峰煎潎涓嶅彉鐨勭墿鍝侊紝鐒跺悗姹傝В榪欎釜01鑳屽寘闂銆傝繖鏍峰畬鍏ㄦ病鏈夋敼榪涘熀鏈濊礬鐨勬椂闂村鏉傚害錛屼絾榪欐瘯绔熺粰浜嗘垜浠皢瀹屽叏鑳屽寘闂杞寲涓?1鑳屽寘闂鐨勬濊礬錛氬皢涓縐嶇墿鍝佹媶鎴愬浠剁墿鍝併?/p>
鏇撮珮鏁堢殑杞寲鏂規(guī)硶鏄細(xì)鎶婄i縐嶇墿鍝佹媶鎴愯垂鐢ㄤ負(fù)c[i]*2^k銆佷環(huán)鍊間負(fù)w[i]*2^k鐨勮嫢騫蹭歡鐗╁搧錛屽叾涓璳婊¤凍c[i]*2^k<=V銆傝繖鏄簩榪涘埗鐨勬濇兂錛屽洜涓轟笉綆℃渶浼樼瓥鐣ラ夊嚑浠剁i縐嶇墿鍝侊紝鎬誨彲浠ヨ〃紺烘垚鑻ュ共涓?^k浠剁墿鍝佺殑鍜屻傝繖鏍鋒妸姣忕鐗╁搧鎷嗘垚O(log V/c[i])浠剁墿鍝侊紝鏄竴涓緢澶х殑鏀硅繘銆?/p>
浣嗘垜浠湁鏇翠紭鐨凮(VN)鐨勭畻娉曘?/p>
O(VN)鐨勭畻娉?br>榪欎釜綆楁硶浣跨敤涓緇存暟緇勶紝鍏堢湅浼唬鐮侊細(xì)
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
浣犱細(xì)鍙戠幇錛岃繖涓吉浠ｇ爜涓嶱01鐨勪吉浠ｇ爜鍙湁v鐨勫驚鐜搴忎笉鍚岃屽凡銆備負(fù)浠涔堣繖鏍蜂竴鏀瑰氨鍙鍛紵棣栧厛鎯蟲兂涓轟粈涔圥01涓鎸夌収v=V..0鐨勯嗗簭鏉ュ驚鐜傝繖鏄洜涓鴻淇濊瘉絎琲嬈″驚鐜腑鐨勭姸鎬乫[i][v]鏄敱鐘舵乫[i-1][v-c[i]]閫掓帹鑰屾潵銆傛崲鍙ヨ瘽璇達(dá)紝榪欐鏄負(fù)浜嗕繚璇佹瘡浠剁墿鍝佸彧閫変竴嬈★紝淇濊瘉鍦ㄨ冭檻“閫夊叆絎琲浠剁墿鍝?#8221;榪欎歡絳栫暐鏃訛紝渚濇嵁鐨勬槸涓涓粷鏃犲凡緇忛夊叆絎琲浠剁墿鍝佺殑瀛愮粨鏋渇[i-1][v-c[i]]銆傝岀幇鍦ㄥ畬鍏ㄨ儗鍖呯殑鐗圭偣鎭版槸姣忕鐗╁搧鍙夋棤闄愪歡錛屾墍浠ュ湪鑰冭檻“鍔犻変竴浠剁i縐嶇墿鍝?#8221;榪欑絳栫暐鏃訛紝鍗存闇瑕佷竴涓彲鑳藉凡閫夊叆絎琲縐嶇墿鍝佺殑瀛愮粨鏋渇[i][v-c[i]]錛屾墍浠ュ氨鍙互騫朵笖蹇呴』閲囩敤v=0..V鐨勯『搴忓驚鐜傝繖灝辨槸榪欎釜綆鍗曠殑紼嬪簭涓轟綍鎴愮珛鐨勯亾鐞嗐?/p>
鍊煎緱涓鎻愮殑鏄紝涓婇潰鐨勪吉浠ｇ爜涓袱灞俧or寰幆鐨勬搴忓彲浠ラ鍊掋傝繖涓粨璁烘湁鍙兘浼?xì)甯︽潵绠楁硶鏃堕棿甯告曨C笂鐨勪紭鍖栥?/p>
榪欎釜綆楁硶涔熷彲浠ヤ互鍙﹀鐨勬濊礬寰楀嚭銆備緥濡傦紝灝嗗熀鏈濊礬涓眰瑙[i][v-c[i]]鐨勭姸鎬佽漿縐繪柟紼嬫樉寮忓湴鍐欏嚭鏉ワ紝浠ｅ叆鍘熸柟紼嬩腑錛屼細(xì)鍙戠幇璇ユ柟紼嬪彲浠ョ瓑浠峰湴鍙樺艦鎴愯繖縐嶅艦寮忥細(xì)
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
灝嗚繖涓柟紼嬬敤涓緇存暟緇勫疄鐜幫紝渚垮緱鍒頒簡涓婇潰鐨勪吉浠ｇ爜銆?/p>
鏈鍚庢娊璞″嚭澶勭悊涓浠跺畬鍏ㄨ儗鍖呯被鐗╁搧鐨勮繃紼嬩吉浠ｇ爜錛?/p>
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
鎬葷粨
瀹屽叏鑳屽寘闂涔熸槸涓涓浉褰撳熀紜鐨勮儗鍖呴棶棰橈紝瀹冩湁涓や釜鐘舵佽漿縐繪柟紼嬶紝鍒嗗埆鍦?#8220;鍩烘湰鎬濊礬”浠ュ強(qiáng)“O(VN)鐨勭畻娉?#8220;鐨勫皬鑺備腑緇欏嚭銆傚笇鏈涗綘鑳藉瀵硅繖涓や釜鐘舵佽漿縐繪柟紼嬮兘浠旂粏鍦頒綋浼?xì)锛屼笉浠呰C綇錛屼篃瑕佸紕鏄庣櫧瀹冧滑鏄庝箞寰楀嚭鏉ョ殑錛屾渶濂借兘澶熻嚜宸辨兂涓縐嶅緱鍒拌繖浜涙柟紼嬬殑鏂規(guī)硶銆備簨瀹炰笂錛屽姣忎竴閬撳姩鎬佽鍒掗鐩兘鎬濊冨叾鏂圭▼鐨勬剰涔変互鍙?qiáng)濡備綍寰楁潵锛屾槸鍔犳繁瀵瑰姩鎬佽鍒掔殑鐞嗚В銆佹彁楂樺姩鎬佽鍒掑姛鍔涚殑濂芥柟娉曘?/p>
絎笁璁?澶氶噸鑳屽寘闂
姣忕鐗╁搧鏈変竴涓浐瀹氱殑嬈℃暟涓婇檺銆?br>P03: 澶氶噸鑳屽寘闂
棰樼洰
鏈塏縐嶇墿鍝佸拰涓涓閲忎負(fù)V鐨勮儗鍖呫傜i縐嶇墿鍝佹渶澶氭湁n[i]浠跺彲鐢紝姣忎歡璐圭敤鏄痗[i]錛屼環(huán)鍊兼槸w[i]銆傛眰瑙ｅ皢鍝簺鐗╁搧瑁呭叆鑳屽寘鍙嬌榪欎簺鐗╁搧鐨勮垂鐢ㄦ誨拰涓嶈秴榪囪儗鍖呭閲忥紝涓斾環(huán)鍊兼誨拰鏈澶с?/p>
鍩烘湰綆楁硶
榪欓鐩拰瀹屽叏鑳屽寘闂寰堢被浼箋傚熀鏈殑鏂圭▼鍙渶灝嗗畬鍏ㄨ儗鍖呴棶棰樼殑鏂圭▼鐣ュ井涓鏀瑰嵆鍙紝鍥犱負(fù)瀵逛簬絎琲縐嶇墿鍝佹湁n[i]+1縐嶇瓥鐣ワ細(xì)鍙?浠訛紝鍙?浠?#8230;…鍙杗[i]浠躲備護(hù)f[i][v]琛ㄧず鍓峣縐嶇墿鍝佹伆鏀懼叆涓涓閲忎負(fù)v鐨勮儗鍖呯殑鏈澶ф潈鍊鹼紝鍒欐湁鐘舵佽漿縐繪柟紼嬶細(xì)
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
澶嶆潅搴︽槸O(V*Σn[i])銆?/p>
杞寲涓?1鑳屽寘闂
鍙︿竴縐嶅ソ鎯沖ソ鍐欑殑鍩烘湰鏂規(guī)硶鏄漿鍖栦負(fù)01鑳屽寘姹傝В錛氭妸絎琲縐嶇墿鍝佹崲鎴恘[i]浠?1鑳屽寘涓殑鐗╁搧錛屽垯寰楀埌浜嗙墿鍝佹暟涓?#931;n[i]鐨?1鑳屽寘闂錛岀洿鎺ユ眰瑙ｏ紝澶嶆潅搴︿粛鐒舵槸O(V*Σn[i])銆?/p>
浣嗘槸鎴戜滑鏈熸湜灝嗗畠杞寲涓?1鑳屽寘闂涔嬪悗鑳藉鍍忓畬鍏ㄨ儗鍖呬竴鏍烽檷浣庡鏉傚害銆備粛鐒惰冭檻浜岃繘鍒剁殑鎬濇兂錛屾垜浠冭檻鎶婄i縐嶇墿鍝佹崲鎴愯嫢騫蹭歡鐗╁搧錛屼嬌寰楀師闂涓i縐嶇墿鍝佸彲鍙栫殑姣忕絳栫暐鈥斺斿彇0..n[i]浠垛斺斿潎鑳界瓑浠蜂簬鍙栬嫢騫蹭歡浠ｆ崲浠ュ悗鐨勭墿鍝併傚彟澶栵紝鍙栬秴榪噉[i]浠剁殑絳栫暐蹇呬笉鑳藉嚭鐜般?/p>
鏂規(guī)硶鏄細(xì)灝嗙i縐嶇墿鍝佸垎鎴愯嫢騫蹭歡鐗╁搧錛屽叾涓瘡浠剁墿鍝佹湁涓涓郴鏁幫紝榪欎歡鐗╁搧鐨勮垂鐢ㄥ拰浠峰煎潎鏄師鏉ョ殑璐圭敤鍜屼環(huán)鍊間箻浠ヨ繖涓郴鏁般備嬌榪欎簺緋繪暟鍒嗗埆涓?,2,4,...,2^(k-1),n[i]-2^k+1錛屼笖k鏄弧瓚硁[i]-2^k+1>0鐨勬渶澶ф暣鏁般備緥濡傦紝濡傛灉n[i]涓?3錛屽氨灝嗚繖縐嶇墿鍝佸垎鎴愮郴鏁板垎鍒負(fù)1,2,4,6鐨勫洓浠剁墿鍝併?/p>
鍒嗘垚鐨勮繖鍑犱歡鐗╁搧鐨勭郴鏁板拰涓簄[i]錛岃〃鏄庝笉鍙兘鍙栧浜巒[i]浠剁殑絎琲縐嶇墿鍝併傚彟澶栬繖縐嶆柟娉曚篃鑳戒繚璇佸浜?..n[i]闂寸殑姣忎竴涓暣鏁幫紝鍧囧彲浠ョ敤鑻ュ共涓郴鏁扮殑鍜岃〃紺猴紝榪欎釜璇佹槑鍙互鍒?..2^k-1鍜?^k..n[i]涓ゆ鏉ュ垎鍒璁哄緱鍑猴紝騫朵笉闅撅紝甯屾湜浣犺嚜宸辨濊冨皾璇曚竴涓嬨?/p>
榪欐牱灝卞皢絎琲縐嶇墿鍝佸垎鎴愪簡O(log n[i])縐嶇墿鍝侊紝灝嗗師闂杞寲涓轟簡澶嶆潅搴︿負(fù)<math>O(V*Σlog n[i])鐨?1鑳屽寘闂錛屾槸寰堝ぇ鐨勬敼榪涖?/p>
涓嬮潰緇欏嚭O(log amount)鏃墮棿澶勭悊涓浠跺閲嶈儗鍖呬腑鐗╁搧鐨勮繃紼嬶紝鍏朵腑amount琛ㄧず鐗╁搧鐨勬暟閲忥細(xì)
procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
甯屾湜浣犱粩緇嗕綋浼?xì)杩欎釜浼唬鐮佸Q屽鏋滀笉澶悊瑙ｇ殑璇濓紝涓嶅Θ緲昏瘧鎴愮▼搴忎唬鐮佷互鍚庯紝鍗曟鎵ц鍑犳錛屾垨鑰呭ご鑴戝姞綰哥瑪妯℃嫙涓涓嬶紝涔熻灝變細(xì)鎱㈡參鐞嗚В浜嗐?/p>
O(VN)鐨勭畻娉?br>澶氶噸鑳屽寘闂鍚屾牱鏈塐(VN)鐨勭畻娉曘傝繖涓畻娉曞熀浜庡熀鏈畻娉曠殑鐘舵佽漿縐繪柟紼嬶紝浣嗗簲鐢ㄥ崟璋冮槦鍒楃殑鏂規(guī)硶浣挎瘡涓姸鎬佺殑鍊煎彲浠ヤ互鍧囨憡O(1)鐨勬椂闂存眰瑙ｃ傜敱浜庣敤鍗曡皟闃熷垪浼樺寲鐨凞P宸茶秴鍑轟簡NOIP鐨勮寖鍥達(dá)紝鏁呮湰鏂囦笉鍐嶅睍寮璁茶В銆傛垜鏈鍒濅簡瑙ｅ埌榪欎釜鏂規(guī)硶鏄湪妤煎ぉ鎴愮殑“鐢蜂漢鍏”騫葷伅鐗囦笂銆?/p>
灝忕粨
榪欓噷鎴戜滑鐪嬪埌浜嗗皢涓涓畻娉曠殑澶嶆潅搴︾敱O(jiān)(V*Σn[i])鏀硅繘鍒癘(V*Σlog n[i])鐨勮繃紼嬶紝榪樼煡閬撲簡瀛樺湪搴旂敤瓚呭嚭NOIP鑼冨洿鐨勭煡璇嗙殑O(VN)綆楁硶銆傚笇鏈涗綘鐗瑰埆娉ㄦ剰“鎷嗗垎鐗╁搧”鐨勬濇兂鍜屾柟娉曪紝鑷繁璇佹槑涓涓嬪畠鐨勬紜э紝騫跺皢瀹屾暣鐨勭▼搴忎唬鐮佸啓鍑烘潵銆?/p>
棰樼洰濡備笅錛?br>瀵逛簬浠?鍒癗鐨勮繛緇暣闆嗗悎鍚堬紝鑳藉垝鍒嗘垚涓や釜瀛愰泦鍚堬紝涓斾繚璇佹瘡涓泦鍚堢殑鏁板瓧鍜屾槸鐩哥瓑鐨勩?br>涓句釜渚嬪瓙錛屽鏋淣=3錛屽浜巤1錛?錛?}鑳藉垝鍒嗘垚涓や釜瀛愰泦鍚堬紝浠栦滑姣忎釜鐨勬墍鏈夋暟瀛楀拰鏄浉絳夌殑錛?br>and {1,2}
榪欐槸鍞竴涓縐嶅垎鍙戯紙浜ゆ崲闆嗗悎浣嶇疆琚涓烘槸鍚屼竴縐嶅垝鍒嗘柟妗堬紝鍥犳涓嶄細(xì)澧炲姞鍒掑垎鏂規(guī)鎬繪暟錛?br>濡傛灉N=7錛屾湁鍥涚鏂規(guī)硶鑳藉垝鍒嗛泦鍚坽1錛?錛?錛?錛?錛?錛?}錛屾瘡涓縐嶅垎鍙戠殑瀛愰泦鍚堝悇鏁板瓧鍜屾槸鐩哥瓑鐨?
{1,6,7} and {2,3,4,5} {娉?1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
緇欏嚭N錛屼綘鐨勭▼搴忓簲璇ヨ緭鍑哄垝鍒嗘柟妗堟繪暟錛屽鏋滀笉瀛樺湪榪欐牱鐨勫垝鍒嗘柟妗堬紝鍒欒緭鍑?銆傜▼搴忎笉鑳介瀛樼粨鏋滅洿鎺ヨ緭鍑恒?br>PROGRAM NAME: subset
INPUT FORMAT
杈撳叆鏂囦歡鍙湁涓琛岋紝涓斿彧鏈変竴涓暣鏁癗
SAMPLE INPUT (file subset.in)
7
OUTPUT FORMAT
杈撳嚭鍒掑垎鏂規(guī)鎬繪暟錛屽鏋滀笉瀛樺湪鍒欒緭鍑?銆?br>SAMPLE OUTPUT (file subset.out)
4
鍙傝冪▼搴忓涓嬶細(xì)
#include <fstream>
using namespace std;
const unsigned int MAX_SUM = 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("subset.in");
ofstream fout ("subset.out");
int main() {
fin >> n;
fin.close();
int s = n*(n+1);
if (s % 4) {
fout << 0 << endl;
fout.close ();
return ;
}
s /= 4;
int i, j;
dyn [0] = 1;
for (i = 1; i <= n; i++)
for (j = s; j >= i; j--)
dyn[j] += dyn[j-i];
fout << (dyn[s]/2) << endl;
fout.close();
return 0;
}
USACO 2.3
Longest Prefix
棰樼洰濡備笅錛?br>鍦ㄧ敓鐗╁涓紝涓浜涚敓鐗╃殑緇撴瀯鏄敤鍖呭惈鍏惰绱犵殑澶у啓瀛楁瘝搴忓垪鏉ヨ〃紺虹殑銆傜敓鐗╁瀹跺浜庢妸闀跨殑搴忓垪鍒嗚В鎴愯緝鐭殑錛堢О涔嬩負(fù)鍏冪礌鐨勶級搴忓垪寰堟劅鍏磋叮銆?
濡傛灉涓涓泦鍚?P 涓殑鍏冪礌鍙互閫氳繃涓茶仈錛堝厑璁?dāng)R噸澶嶏紱涓茶仈錛岀浉褰撲簬 Pascal 涓殑 “+” 榪愮畻絎︼級緇勬垚涓涓簭鍒?S 錛岄偅涔堟垜浠涓哄簭鍒?S 鍙互鍒嗚В涓?P 涓殑鍏冪礌銆傚茍涓嶆槸鎵鏈夌殑鍏冪礌閮藉繀欏誨嚭鐜般備婦涓緥瀛愶紝搴忓垪 ABABACABAAB 鍙互鍒嗚В涓轟笅闈㈤泦鍚堜腑鐨勫厓绱狅細(xì)
{A, AB, BA, CA, BBC}
搴忓垪 S 鐨勫墠闈?K 涓瓧絎︾О浣?S 涓暱搴︿負(fù) K 鐨勫墠緙銆傝璁′竴涓▼搴忥紝杈撳叆涓涓厓绱犻泦鍚堜互鍙?qiáng)涓涓ぇ鍐欏瓧姣嶅簭鍒楋紝璁＄畻榪欎釜搴忓垪鏈闀跨殑鍓嶇紑鐨勯暱搴︺?
PROGRAM NAME: prefix
INPUT FORMAT
杈撳叆鏁版嵁鐨勫紑澶村寘鎷?1..200 涓厓绱狅紙闀垮害涓?1..10 錛夌粍鎴愮殑闆嗗悎錛岀敤榪炵畫鐨勪互絀烘牸鍒嗗紑鐨勫瓧絎︿覆琛ㄧず銆傚瓧姣嶅叏閮ㄦ槸澶у啓錛屾暟鎹彲鑳戒笉姝竴琛屻傚厓绱犻泦鍚堢粨鏉熺殑鏍囧織鏄竴涓彧鍖呭惈涓涓?“.” 鐨勮銆傞泦鍚堜腑鐨勫厓绱犳病鏈夐噸澶嶃傛帴鐫鏄ぇ鍐欏瓧姣嶅簭鍒?S 錛岄暱搴︿負(fù) 1..200,000 錛岀敤涓琛屾垨鑰呭琛岀殑瀛楃涓叉潵琛ㄧず錛屾瘡琛屼笉瓚呰繃 76 涓瓧絎︺傛崲琛岀騫朵笉鏄簭鍒?S 鐨勪竴閮ㄥ垎銆?br>SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
鍙湁涓琛岋紝杈撳嚭涓涓暣鏁幫紝琛ㄧず S 鑳藉鍒嗚В鎴?P 涓厓绱犵殑鏈闀垮墠緙鐨勯暱搴︺?br>SAMPLE OUTPUT (file prefix.out)
11
紺轟緥紼嬪簭濡備笅錛?br>
#include <stdio.h>
/* maximum number of primitives */
#define MAXP 200
/* maximum length of a primitive */
#define MAXL 10
char prim[MAXP+1][MAXL+1]; /* primitives */
int nump; /* number of primitives */
int start[200001]; /* is this prefix of the sequence expressible? */
char data[200000]; /* the sequence */
int ndata; /* length of the sequence */
int main(int argc, char **argv)
{
FILE *fout, *fin;
int best;
int lv, lv2, lv3;
if ((fin = fopen("prim.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("prim.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
/* read in primitives */
while (1)
{
fscanf (fin, "%s", prim[nump]);
if (prim[nump][0] != '.') nump++;
else break;
}
/* read in string, one line at a time */
ndata = 0;
while (fscanf (fin, "%s", data+ndata) == 1)
ndata += strlen(data+ndata);
start[0] = 1;
best = 0;
for (lv = 0; lv < ndata; lv++)
if (start[lv])
{ /* for each expressible prefix */
best = lv; /* we found a longer expressible prefix! */
/* for each primitive, determine the the sequence starting at
this location matches it */
for (lv2 = 0; lv2 < nump; lv2++)
{
for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] &&
prim[lv2][lv3] == data[lv+lv3]; lv3++)
;
if (!prim[lv2][lv3]) /* it matched! */
start[lv + lv3] = 1; /* so the expanded prefix is also expressive */
}
}
/* see if the entire sequence is expressible */
if (start[ndata]) best = ndata;
fprintf (fout, "%i\n", best);
return 0;
}
USACO 3.1
Score Inflation
棰樼洰濡備笅錛?br>鎴戜滑璇曠潃璁捐鎴戜滑鐨勭珵璧涗互渚夸漢浠兘灝藉彲鑳界殑澶氬緱鍒?榪欓渶瑕佷綘鐨勫府鍔┿?br>鎴戜滑鍙互浠庡嚑涓綾諱腑閫夊彇绔炶禌鐨勯鐩?榪欓噷鐨勪竴涓?縐嶇被"鏄寚涓涓珵璧涢鐩殑闆嗗悎,瑙ｅ喅闆嗗悎涓殑棰樼洰闇瑕佺浉鍚屽鐨勬椂闂村茍涓旇兘寰楀埌鐩稿悓鐨勫垎鏁般?br>浣犵殑浠誨姟鏄啓涓涓▼搴忔潵鍛婅瘔USACO鐨勮亴鍛?搴旇浠庢瘡涓涓綾諱腑閫夊彇澶氬皯棰樼洰,浣垮緱瑙ｅ喅棰樼洰鐨勬昏楁椂鍦ㄧ珵璧涜瀹氱殑鏃墮棿閲屽茍涓旀誨垎鏈澶с?br>杈撳叆鍖呮嫭绔炶禌鐨勬椂闂?M(1 <= M <= 10,000)鍜孨,"縐嶇被"鐨勬暟鐩? <= N <= 10,000銆?br>鍚庨潰鐨勬瘡涓琛屽皢鍖呮嫭涓や釜鏁存暟鏉ユ弿榪頒竴涓?縐嶇被":
絎竴涓暣鏁拌鏄庤В鍐寵繖縐嶉鐩兘寰楃殑鍒嗘暟(1 <= points <= 10000),絎簩鏁存暟璇存槑瑙ｅ喅榪欑棰樼洰鎵闇鐨勬椂闂?1 <= minutes <= 10000)銆?br>浣犵殑紼嬪簭搴旇紜畾鎴戜滑搴旇浠庢瘡涓?縐嶇被"涓夊灝戦亾棰樼洰浣垮緱鑳藉湪绔炶禌鐨勬椂闂翠腑寰楀埌鏈澶х殑鍒嗘暟銆?br>鏉ヨ嚜浠繪剰鐨?縐嶇被"鐨勯鐩暟鐩彲鑳戒換浣曢潪璐熸暟(0鎴栨洿澶?銆?br>璁＄畻鍙兘寰楀埌鐨勬渶澶у垎鏁般?br>PROGRAM NAME: inflate
INPUT FORMAT
絎?1 琛? M, N--绔炶禌鐨勬椂闂村拰棰樼洰"縐嶇被"鐨勬暟鐩?
絎?2-N+1 琛? 涓や釜鏁存暟:姣忎釜"縐嶇被"棰樼洰鐨勫垎鏁板拰鑰楁椂銆?
SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
鍗曠嫭鐨勪竴琛屽寘鎷偅涓湪緇欏畾鐨勯檺鍒墮噷鍙兘寰楀埌鐨勬渶澶х殑鍒嗘暟銆?br>SAMPLE OUTPUT (file inflate.out)
605
{浠庣2涓?縐嶇被"涓変袱棰橈紝絎?涓?縐嶇被"涓変笁棰榼
紺轟緥紼嬪簭濡備笅錛?br>
#include <fstream.h>
ifstream fin("inflate.in");
ofstream fout("inflate.out");
const short maxm = 10010;
long best[maxm], m, n;
void
main()
{
short i, j, len, pts;
fin >> m >> n;
for (j = 0; j <= m; j++)
best[j] = 0;
for (i = 0; i < n; i++) {
fin >> pts >> len;
for (j = len; j <= m; j++)
if (best[j-len] + pts > best[j])
best[j] = best[j-len] + pts;
}
fout << best[m] << endl; // 鐢變簬鏁扮粍鍏冪礌涓嶅噺錛屾湯鍏冪礌鏈澶?br>}
USACO 3.3
A Game
棰樼洰濡備笅錛?br>鏈夊涓嬩竴涓弻浜烘父鎴?N(2 <= N <= 100)涓鏁存暟鐨勫簭鍒楁斁鍦ㄤ竴涓父鎴忓鉤鍙頒笂錛屼袱浜鴻疆嫻佷粠搴忓垪鐨勪袱绔彇鏁幫紝鍙栨暟鍚庤鏁板瓧琚幓鎺夊茍绱姞鍒版湰鐜╁鐨勫緱鍒嗕腑錛屽綋鏁板彇灝芥椂錛屾父鎴忕粨鏉熴備互鏈緇堝緱鍒嗗鑰呬負(fù)鑳溿?
緙栦竴涓墽琛屾渶浼樼瓥鐣ョ殑紼嬪簭錛屾渶浼樼瓥鐣ュ氨鏄嬌鑷繁鑳藉緱鍒板湪褰撳墠鎯呭喌涓嬫渶澶х殑鍙兘鐨勬誨垎鐨勭瓥鐣ャ備綘鐨勭▼搴忚濮嬬粓涓虹浜屼綅鐜╁鎵ц鏈浼樼瓥鐣ャ?br>PROGRAM NAME: game1
INPUT FORMAT
絎竴琛? 姝ｆ暣鏁癗, 琛ㄧず搴忓垪涓鏁存暟鐨勪釜鏁般?
絎簩琛岃嚦鏈熬: 鐢ㄧ┖鏍煎垎闅旂殑N涓鏁存暟錛堝ぇ灝忎負(fù)1-200錛夈?
SAMPLE INPUT (file game1.in)
6
4 7 2 9
5 2
OUTPUT FORMAT
鍙湁涓琛岋紝鐢ㄧ┖鏍煎垎闅旂殑涓や釜鏁存暟: 渚濇涓虹帺瀹朵竴鍜岀帺瀹朵簩鏈緇堢殑寰楀垎銆?
SAMPLE OUTPUT (file game1.out)
18 11
鍙傝冪▼搴忓涓嬶細(xì)
#include <stdio.h>
#define NMAX 101
int best[NMAX][2], t[NMAX];
int n;
void
readx () {
int i, aux;
freopen ("game1.in", "r", stdin);
scanf ("%d", &n);
for (i = 1; i <= n; i++) {
scanf ("%d", &aux);
t = t[i - 1] + aux;
}
fclose (stdin);
}
inline int
min (int x, int y) {
return x > y ? y : x;
}
void
solve () {
int i, l;
for (l = 1; l <= n; l++)
for (i = 1; i + l <= n + 1; i++)
best[l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],
best[(l - 1) % 2]);
}
void writex () {
freopen ("game1.out", "w", stdout);
printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);
fclose (stdout);
}
int
main () {
readx ();
solve ();
writex ();
return 0;
}
USACO 3.4
Raucous Rockers
棰樼洰濡備笅錛?br>浣犲垰鍒氬緱鍒頒簡嫻佽鐨?#8220;鐮撮敚鎽囨粴”涔愰槦褰曞埗鐨勫皻鏈彂琛ㄧ殑N(1 <= N <= 20)棣栨瓕鐨勭増鏉冦備綘鎵撶畻浠庝腑綺鵑変竴浜涙瓕鏇詫紝鍙戣M(1 <= M <= 20)寮燙D銆傛瘡涓寮燙D鏈澶氬彲浠ュ綰砊(1 <= T <= 20)鍒嗛挓鐨勯煶涔愶紝涓棣栨瓕涓嶈兘鍒嗚鍦ㄤ袱寮燙D涓?
涓嶅閥浣犳槸涓浣嶅彜鍏擱煶涔愯糠錛屼笉鎳傚浣曞垽瀹氳繖浜涙瓕鐨勮壓鏈環(huán)鍊箋備簬鏄綘鍐沖畾鏍規(guī)嵁浠ヤ笅鏍囧噯榪涜閫夋嫨錛?
姝屾洸蹇呴』鎸夌収鍒涗綔鐨勬椂闂撮『搴忓湪CD鐩樹笂鍑虹幇銆?
閫変腑鐨勬瓕鏇叉暟鐩敖鍙兘鍦板銆?
PROGRAM NAME: rockers
INPUT FORMAT
絎竴琛岋細(xì) 涓変釜鏁存暟錛歂, T, M.
絎簩琛岋細(xì) N涓暣鏁幫紝鍒嗗埆琛ㄧず姣忛姝岀殑闀垮害錛屾寜鍒涗綔鏃墮棿欏哄簭鎺掑垪銆?
SAMPLE INPUT (file rockers.in)
4 5 2
4 3 4 2
OUTPUT FORMAT
涓涓暣鏁幫紝琛ㄧず鍙互瑁呰繘M寮燙D鐩樼殑涔愭洸鐨勬渶澶ф暟鐩?
SAMPLE OUTPUT (file rockers.out)
3
鍙傝冪▼搴忓涓嬶細(xì)
#include <stdio.h>
#define MAX 25
int dp[MAX][MAX][MAX], length[MAX];
int
main ()
{
FILE *in = fopen ("rockers.in", "r");
FILE *out = fopen ("rockers.out", "w");
int a, b, c, d, best, numsongs, cdlength, numcds;
fscanf (in, "%d%d%d", &numsongs, &cdlength, &numcds);
for (a = 1; a <= numsongs; a++)
fscanf (in, "%d", &length[a]);
best = 0;
for (a = 0; a < numcds; a++)/*褰撳墠cd */
for (b = 0; b <= cdlength; b++) /* 宸茶繃鐨勬椂闂?/
for (c = 0; c <= numsongs; c++) { /* 涓婁竴鏇?/
for (d = c + 1; d <= numsongs; d++) { /* 涓嬩竴鏇?/
if (b + length[d] <= cdlength) {
if (dp[a][c] + 1 > dp[a][b + length[d]][d])
dp[a][b + length[d]][d] = dp[a][c] + 1;
}
else {
if (dp[a][c] + 1 > dp[a + 1][length[d]][d])
dp[a + 1][length[d]][d] = dp[a][c] + 1;
}
}
if (dp[a][c] > best)
best = dp[a][c];
}
fprintf (out, "%d\n", best);
return 0;
}
USACO
4.3 Buy Low, Buy Lower
“閫綆鍚哥撼”鏄倰鑲＄殑涓鏉℃垚鍔熺璇銆傚鏋滀綘鎯蟲垚涓轟竴涓垚鍔熺殑鎶曡祫鑰咃紝灝辮閬靛畧榪欐潯縐樿瘈:
"閫綆鍚哥撼,瓚婁綆瓚婁拱"
榪欏彞璇濈殑鎰忔濇槸錛氭瘡嬈′綘璐拱鑲＄エ鏃剁殑鑲′環(huán)涓瀹氳姣斾綘涓婃璐拱鏃剁殑鑲′環(huán)浣?鎸夌収榪欎釜瑙勫垯璐拱鑲＄エ鐨勬鏁拌秺澶氳秺濂斤紝鐪嬬湅浣犳渶澶氳兘鎸夎繖涓鍒欎拱鍑犳銆?br>緇欏畾榪炵畫鐨凬澶╀腑姣忓ぉ鐨勮偂浠楓備綘鍙互鍦ㄤ換浣曚竴澶╄喘涔頒竴嬈¤偂紲紝浣嗘槸璐拱鏃剁殑鑲′環(huán)涓瀹氳姣斾綘涓婃璐拱鏃剁殑鑲′環(huán)浣庛傚啓涓涓▼搴忥紝姹傚嚭鏈澶氳兘涔板嚑嬈¤偂紲ㄣ?
浠ヤ笅闈㈣繖涓〃涓轟緥, 鏌愬嚑澶╃殑鑲′環(huán)鏄?
澶╂暟 1 2 3 4 5 6 7 8 9 10 11 12
鑲′環(huán) 68 69 54 64 68 64 70 67 78 62 98 87
榪欎釜渚嬪瓙涓? 鑱槑鐨勬姇璧勮?鎸変笂闈㈢殑瀹氫箟)錛屽鏋滄瘡嬈′拱鑲＄エ鏃剁殑鑲′環(huán)閮芥瘮涓婁竴嬈′拱鏃朵綆錛岄偅涔堜粬鏈澶氳兘涔?嬈¤偂紲ㄣ備竴縐嶄拱娉曞涓?鍙兘鏈夊叾浠栫殑涔版硶):
澶╂暟 2 5 6 10
鑲′環(huán) 69 68 64 62
PROGRAM NAME: buylow
INPUT FORMAT
絎?琛? N (1 <= N <= 5000), 琛ㄧず鑳戒拱鑲＄エ鐨勫ぉ鏁般?
絎?琛屼互涓? N涓鏁存暟 (鍙兘鍒嗗琛? 錛岀i涓鏁存暟琛ㄧず絎琲澶╃殑鑲′環(huán). 榪欎簺姝ｆ暣鏁板ぇ灝忎笉浼?xì)瓒厴q噇ongint(pascal)/long(c++).
SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
OUTPUT FORMAT
鍙湁涓琛岋紝杈撳嚭涓や釜鏁存暟錛?
鑳藉涔拌繘鑲＄エ鐨勫ぉ鏁?
闀垮害杈懼埌榪欎釜鍊肩殑鑲＄エ璐拱鏂規(guī)鏁伴噺
鍦ㄨ綆楄В鐨勬暟閲忕殑鏃跺欙紝濡傛灉涓や釜瑙ｆ墍緇勬垚鐨勫瓧絎︿覆鐩稿悓錛岄偅涔堣繖鏍風(fēng)殑涓や釜瑙ｈ璁や負(fù)鏄浉鍚岀殑錛堝彧鑳界畻鍋氫竴涓В錛夈傚洜姝わ紝涓や釜涓嶅悓鐨勮喘涔版柟妗堝彲鑳戒駭鐢熷悓涓涓瓧絎︿覆錛岃繖鏍峰彧鑳借綆椾竴嬈°?
SAMPLE OUTPUT (file buylow.out)
4 2
鍙傝冪▼搴忓涓嬶細(xì)
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct BIGNUM *bignum_t;
struct BIGNUM
{
int val;
bignum_t next;
};
int num[5000];
int len[5000];
int nlen;
bignum_t cnt[5000];
bignum_t get_big(void)
{
static bignum_t block;
static int size = 0;
if (size == 0)
{
block = (bignum_t)malloc(sizeof(*block)*128);
size = 128;
}
size--;
return block++;
}
/*鍒濆鍖栭珮綺懼害鏁?/
void init_big(bignum_t *num, int val)
{
*num = get_big();
/* initialize */
(*num)->val = val;
(*num)->next = NULL;
}
void add(bignum_t a, bignum_t b)
{
int c; /* carry */
c = 0;
while (b || c)
{
a->val += c;
if (b) a->val += b->val;
/* if a->val is too large, we need to carry */
c = (a->val / 1000000);
a->val = (a->val % 1000000);
if (b) b = b->next;
if (!a->next && (b || c))
{ /* allocate if we need to */
a->next = get_big();
a = a->next;
a->val = 0;
a->next = NULL;
} else a = a->next;
}
}
void out_num(FILE *f, bignum_t v)
{
if (v->next)
{
out_num(f, v->next);
fprintf (f, "%06i", v->val);
}
else
fprintf (f, "%i", v->val);
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv, lv2;
int c;
int max;
int l;
bignum_t ans;
if ((fin = fopen("buylow.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("buylow.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d", &nlen);
for (lv = 0; lv < nlen; lv++)
fscanf (fin, "%d", &num[lv]);
/* 鐢―P璁＄畻鏈澶ч暱搴?/
for (lv = 0; lv < nlen; lv++)
{
max = 1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (num[lv2] > num[lv] && len[lv2]+1 > max) max = len[lv2]+1;
len[lv] = max;
}
for (lv = 0; lv < nlen; lv++)
{
if (len[lv] == 1) init_big(&cnt[lv], 1);
else
{
init_big(&cnt[lv], 0);
l = -1;
max = len[lv]-1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (len[lv2] == max && num[lv2] > num[lv] && num[lv2] != l)
add(cnt[lv], cnt[lv2]);
l = num[lv2];
}
}
}
/* 鎵炬渶闀夸覆*/
max = 0;
for (lv = 0; lv < nlen; lv++)
if (len[lv] > max) max = len[lv];
init_big(&ans, 0);
l = -1;
for (lv = nlen-1; lv >= 0; lv--)
if (len[lv] == max && num[lv] != l)
{
add(ans, cnt[lv]);
l = num[lv];
}
/* output answer */
fprintf (fout, "%i ", max);
out_num(fout, ans);
fprintf (fout, "\n");
return 0;
}