is-programmer 2012-02-24 13:57 鍙戣〃璇勮
]]>鏈変漢涓嶅仠鍦拌拷姹傚垢紱忋備粬浠負(fù)浜嗗垢紱忕殑鏃跺埢鎷煎敖鍏ㄥ姏銆備互鑷充簬鍚哥儫錛岄厳閰掞紝涔冭嚦浜庡惛姣掞紝婊ヤ氦錛屽叾瀹炶繖浜涙病鏈夋兂璞＄殑閭ｄ箞涓嶅ソ錛岃嚦灝戝彲浠ョ粰浜轟竴瀹氭椂闂寸殑婊¤凍鎰燂紝騫哥鎰燂紝涓嶇劧涔熷氨涓嶄細(xì)鏈変笉灝戞槑鏄燂紝澶ф鍠滄榪欎簺錛屽彧鏄ぞ浼?xì)鑸嗚鎺掓枼杩欎簺銆傛瀬闄愯繍鍔ㄤ篃鏄紑濮嬪鍙楁帹宕囷紝濡傝功鏋侊紝璺充紴絳夌瓑銆傚彲鏄繖涓鍒囦篃鏄細(xì)榪囧幓鐨勶紝涓嶈繃鍙互緇欎漢涓瀹氭椂闂存槸鍑轟簬騫哥鐨勭姸鎬佺殑銆?br />鍏跺疄鎴戞兂璇翠漢鏍規(guī)湰灝變笉搴旇榪芥眰騫哥錛?br />娌℃湁浠涔堟槸鍙互甯︽潵闀夸箙鐨勫垢紱忔劅鐨勶紒鑾峰緱涔嬪悗灝變細(xì)take it for granted錛?br />鎵浠ユ垜浠鍋氱敇浜庤繃騫蟲貳鏃ュ瓙鐨勪漢錛屼粬浠疄闄呬笂涓嶄細(xì)鍘誨埢鎰忚拷姹傚垢紱忔劅鏈韓錛岃屾槸涓浜涙湁浠峰煎拰鏈夋剰涔夌殑浜嬨傚閲戦挶錛屽搴拰鐫︼紝鑷敱絳夌瓑銆?img src ="http://www.shnenglu.com/nxm1990/aggbug/165692.html" width = "1" height = "1" />
is-programmer 2012-02-15 21:03 鍙戣〃璇勮
]]>榪欓噷鏈夊鐭╅樀榪炰箻闂鐨勬弿榪般傞鍏堝簲璇ュ闂榪涜鎶借薄錛屽鏋滆兘澶熶簡瑙ｉ棶棰樹腑鐭╅樀鐨勯儴鍒嗭紝閭ｄ箞闂鍙互鎶借薄鎴愯繖鏍?a >poj1651銆傝繖閲岄棶棰樼殑鍙︿竴縐嶇畝鍗曠殑琛ㄧず鏂瑰紡灝辨槸錛氱粰瀹氫竴鍒楁暟錛屾瘡嬈′綘鍙互浠庝腑鎶藉彇1涓暟錛堥櫎鍘誨ご灝句袱涓暟涓嶅彲浠ユ娊鍙栵級錛岃緗竴涓猻core錛屽綋浣犳娊鍙栬鏁扮殑鏃跺欙紝score瑕佸姞涓婅鏁板拰宸﹀彸涓や釜鏁扮殑涔樼Н錛岄棶鎶藉彇鍒版渶鍚庡彧鍓╀笅澶村熬涓や釜鏁扮殑鏃跺欙紝鎬庢牱鐨勬娊鍙栭『搴忓彲浠ヤ嬌score鐨勫兼渶灝忓憿錛?br />寰堢洿瑙傜殑鏂規(guī)硶灝辨槸鏋氫婦姣忕鎶藉彇鏂瑰紡錛岀劧鍚庢壘鍑轟嬌score鏈灝忕殑閭ｄ竴嬈℃娊鍙栥傦紙榪欒縐頒負(fù)絎ㄥ姙娉曪級
鍏堣鏈塶涓鎶藉彇鐨勬暟錛屼篃灝辨槸鎬繪暟涓簄+2銆傛垜浠瘯鐫浠庝腑鎶藉彇m涓紝閭ｄ箞鎴戜滑浼?xì)鍙戠幇鍦ㄧ渷涓嬬殑閭ｄ簺杩樻病琚娊鍙栫殑鏁板瓧涓簲璇ュ瓨鍦ㄤ竴縐嶆娊鍙栫瓥鐣ヤ嬌寰楀畠浠殑score鏈灝忥紙鏈浼樺瓙緇撴瀯錛岃繖閲屽彲浠ョ敤綆鍗曠殑鍙嶈瘉娉曡鏄庯級錛屾崲鍙ヨ瘽璇達(dá)紝灝辨槸鎴戜滑鍓嶉潰鎬庢牱鐨勬娊鍙栭『搴忓鍚庨潰涓嶄細(xì)閫犳垚褰卞搷銆傝繖閲屽氨璇存槑浜嗙鍔炴硶涓轟粈涔堢浜嗭細(xì)濡傛灉鎴戜滑鎵懼嚭浜嗗悗闈㈡娊鍙栫殑鏈浼樼瓥鐣ュ悗錛岄偅涔堟瘡嬈℃垜浠敼鍙樺墠闈㈢殑m涓暟鐨勬娊鍙栭『搴忔椂錛屾槸涓嶉渶瑕佸鍚庨潰鎶藉彇欏哄簭榪涜鏋氫婦鐨勶紝鍙湁鐢ㄦ渶浼橀偅涓瓥鐣ュ嵆鍙紙閲嶅彔瀛愰棶棰橈級銆?br />閭ｄ箞榪欐牱璇寸殑璇濓紝鍙鎵懼嚭鍓嶉潰鎶藉彇鐨勬渶浼樼瓥鐣ュ拰鍚庨潰鎶藉彇鐨勬渶浼樼瓥鐣ョ殑璇濓紝閭ｄ箞灝卞彲浠ユ壘鍑鴻繖鏍風(fēng)殑緇撴灉錛氫互鍏堟娊鍙杕涓負(fù)鍒嗙晫闄愮殑鏈浼樿В銆傞偅涔堣姹傛娊鍙杗涓悆鐨勯棶棰樻椂錛屽氨闇瑕佷粠1寮濮嬪埌n/2涓哄垎鐣岄檺鐨勬渶浼樿В銆傜劧鍚庡啀瀵規(guī)瘡涓瓙闂榪涜閫掑綊鐨勬眰瑙ｏ紝褰搉=1鏃墮偅涔堥棶棰樻棤闇鍐嶈繘琛屽垎瑙ｃ?br />涓婇潰榪欐牱瀛愮悊瑙ｆ湁涓己鐐癸細(xì)寰堥毦鐢ㄨ綆楁満璇█瀹炵幇銆傞棶棰樺湪浜庡厛鎶藉彇m涓暟錛岃繖浜涙暟鐨勪綅緗笉榪炵畫銆傚叾瀹炴妸瀹冩敼涓鴻繛緇殑瀵歸鐩殑姹傝В涔熸槸涓鏍風(fēng)殑錛屼笉榪囪繖鏃跺欒鎵劇殑灝變笉鏄粠1鍒皀/2涓哄垎鐣岄檺鐨勬渶浼樿В浜嗭紙榪欐牱鐨勮瘽灝變笉鍏ㄩ潰錛夈傚簲璇ヤ粠寮澶寸殑1錛屼竴鐩村埌n-1榪涜鎵炬渶浼樿В銆?br />榪欐槸poj1651鐨勪唬鐮侊細(xì)
1 #include<iostream>
2 using namespace std;
3 const int inf = 0xffffff;
4 int dp[101][101];
5 int num[101];
6 void input(int n){
7 for(int i = 1 ; i <= n; i++)
8 cin>>num[i];
9 for(int i = 0; i <= n; i++)
10 for(int j = 0 ; j <= n; j++)
11 dp[i][j] = inf;
12 }
13 int solve(int a,int b){
14 if(dp[a][b] != inf)return dp[a][b];
15 if(b - a == 2){
16 dp[a][b] = num[a]*num[a+1]*num[b];
17 return dp[a][b];
18 }
19 if(b - a == 1){
20 dp[a][b] = 0;
21 return dp[a][b];
22 }
23 int min = inf;
24 int temp;
25 for(int i = a+1 ; i < b; i ++){
26 temp = solve(a,i) + solve(i,b) + num[a]*num[i]*num[b];
27 if(temp < min) min = temp;
28 }
29 dp[a][b] = min;
30 return dp[a][b];
31 }
32 int main(){
33 int n;
34 while(cin >> n){
35 input(n);
36 cout << solve(1,n)<<endl;
37 }
38 }
2 using namespace std;
3 const int inf = 0xffffff;
4 int dp[101][101];
5 int num[101];
6 void input(int n){
7 for(int i = 1 ; i <= n; i++)
8 cin>>num[i];
9 for(int i = 0; i <= n; i++)
10 for(int j = 0 ; j <= n; j++)
11 dp[i][j] = inf;
12 }
13 int solve(int a,int b){
14 if(dp[a][b] != inf)return dp[a][b];
15 if(b - a == 2){
16 dp[a][b] = num[a]*num[a+1]*num[b];
17 return dp[a][b];
18 }
19 if(b - a == 1){
20 dp[a][b] = 0;
21 return dp[a][b];
22 }
23 int min = inf;
24 int temp;
25 for(int i = a+1 ; i < b; i ++){
26 temp = solve(a,i) + solve(i,b) + num[a]*num[i]*num[b];
27 if(temp < min) min = temp;
28 }
29 dp[a][b] = min;
30 return dp[a][b];
31 }
32 int main(){
33 int n;
34 while(cin >> n){
35 input(n);
36 cout << solve(1,n)<<endl;
37 }
38 }
is-programmer 2011-12-28 18:45 鍙戣〃璇勮
]]>1錛宧uffman緙栫爜瑕佺敤鍒拌椽蹇冪畻娉曪紝鎵浠ョ敤priority_queue鍙互鍦ㄥ父閲忔椂闂村唴鍙栧嚭鍜屾彃鍏ュ箋?br />2錛岄潤鎬佸緩鏍?wèi)锛?xì)huffman鏍?wèi)鐨勮妭鐐硅〃绀烘栆?guī)硶閲囩敤浜嗘渶澶氱殑鍙橀噺錛屽嵆鐖朵翰鑺傜偣錛屽乏鍙沖瓙鑺傜偣錛堝洜涓虹▼搴忎腑紜疄鏈夎繖縐嶉渶瑕侊紝榪欓噷涓嶅悓涓庝簩鍙夊爢錛屾棤娉曢氳繃鍦ㄩ潤鎬佹爲(wèi)錛堥摼琛級鐨勪綅緗潵紜畾鍏剁埗浜茶妭鐐瑰拰瀛愯妭鐐癸級錛?span style="font-size: 14px; background-color: #eeeeee; color: #008080; ">
1 #include<iostream>
2 #include<cstring>
3 #include<queue>
4 #include<cstdlib>
5 using namespace std;
6 const int MAXSIZE = 27;
7 class huffNode{
8 public:
9 int pr;
10 int lc , rc;
11 char s;
12 int pow;
13 bool operator < (const huffNode& b)const{
14 return pow > b.pow;
15 }
16 };
17 huffNode huff[MAXSIZE * 2];
18 string buf;
19 int count[26];
20 priority_queue<huffNode> greed;
21 //for the sake of convenience , assume that the
22 //standard input is from 'a' to 'z'.
23 int input(){
24 cout << "input the text!"<<endl;
25 cin >> buf;
26 for(int i = 0; i < 26 ; i++) count[i] = 0;
27 memset(huff , 0, sizeof(huff));
28 for(int i = 0; i < buf.length();i++)count[buf[i]-'a']++;
29 int len = 0;
30 for(int i = 0 ,j = 0; i < 26; i++)
31 if(count[i]){
32 huff[j].s = i + 'a';
33 huff[j].pow = count[i];
34 huff[j].pr = j;
35 cout << "the" << ' '<<'\''<< char(i+'a') <<'\''
36 <<' '<<"have arisen for " <<count[i]<<" time(s)"
37 <<endl;
38 greed.push(huff[j]);
39 len = j;
40 j++;
41 }
42 return len;
43 }
44
45 int createTree(int len){
46 if(len == 0) {
47 cout << " Only one kind of alf !"<<endl;
48 exit(1);
49 }
50 huffNode temp1 ,temp2,temp;
51 while(!greed.empty()){
52 temp1 = greed.top();
53 greed.pop();
54 temp2 = greed.top();
55 greed.pop();
56 len ++;
57 temp.lc = temp1.pr;
58 temp.rc = temp2.pr;
59 huff[temp1.pr].pr = huff[temp2.pr].pr = len;
60 temp.pr = len;
61 temp.pow = temp1.pow + temp2.pow;
62 huff[len] = temp;
63 if(!greed.empty()) greed.push(temp);
64 }
65 return len;
66 }
67
68 void reserve(char * a){
69 int len = strlen(a);
70 for(int i = 0 ; i <= len/2 ;i ++)
71 swap(a[i],a[len-i-1]);
72 }
73 struct code{
74 char s;
75 char co[50];
76 };
77
78 void coding(int len1,int len2){
79 code* mycode = new code[len1+1];
80 memset(mycode ,0 ,sizeof(mycode));
81 for(int i = 0; i <= len1 ; i++){
82 int j = i;
83 int t = 0;
84 mycode[i].s = huff[i].s;
85 while(j < len2){
86 if(huff[huff[j].pr].lc == j)
87 mycode[i].co[t++] = '0';
88 else mycode[i].co[t++] = '1';
89 j = huff[j].pr ;
90 }
91 reserve(mycode[i].co);
92 cout << "the code of " << mycode[i].s
93 << " is " << mycode[i].co <<endl;
94 }
95 delete[] mycode;
96 }
97
98 int main(){
99 int len1 = input();
100 int len2 = createTree(len1);
101 coding(len1,len2);
102 }
103
104
105
106
2 #include<cstring>
3 #include<queue>
4 #include<cstdlib>
5 using namespace std;
6 const int MAXSIZE = 27;
7 class huffNode{
8 public:
9 int pr;
10 int lc , rc;
11 char s;
12 int pow;
13 bool operator < (const huffNode& b)const{
14 return pow > b.pow;
15 }
16 };
17 huffNode huff[MAXSIZE * 2];
18 string buf;
19 int count[26];
20 priority_queue<huffNode> greed;
21 //for the sake of convenience , assume that the
22 //standard input is from 'a' to 'z'.
23 int input(){
24 cout << "input the text!"<<endl;
25 cin >> buf;
26 for(int i = 0; i < 26 ; i++) count[i] = 0;
27 memset(huff , 0, sizeof(huff));
28 for(int i = 0; i < buf.length();i++)count[buf[i]-'a']++;
29 int len = 0;
30 for(int i = 0 ,j = 0; i < 26; i++)
31 if(count[i]){
32 huff[j].s = i + 'a';
33 huff[j].pow = count[i];
34 huff[j].pr = j;
35 cout << "the" << ' '<<'\''<< char(i+'a') <<'\''
36 <<' '<<"have arisen for " <<count[i]<<" time(s)"
37 <<endl;
38 greed.push(huff[j]);
39 len = j;
40 j++;
41 }
42 return len;
43 }
44
45 int createTree(int len){
46 if(len == 0) {
47 cout << " Only one kind of alf !"<<endl;
48 exit(1);
49 }
50 huffNode temp1 ,temp2,temp;
51 while(!greed.empty()){
52 temp1 = greed.top();
53 greed.pop();
54 temp2 = greed.top();
55 greed.pop();
56 len ++;
57 temp.lc = temp1.pr;
58 temp.rc = temp2.pr;
59 huff[temp1.pr].pr = huff[temp2.pr].pr = len;
60 temp.pr = len;
61 temp.pow = temp1.pow + temp2.pow;
62 huff[len] = temp;
63 if(!greed.empty()) greed.push(temp);
64 }
65 return len;
66 }
67
68 void reserve(char * a){
69 int len = strlen(a);
70 for(int i = 0 ; i <= len/2 ;i ++)
71 swap(a[i],a[len-i-1]);
72 }
73 struct code{
74 char s;
75 char co[50];
76 };
77
78 void coding(int len1,int len2){
79 code* mycode = new code[len1+1];
80 memset(mycode ,0 ,sizeof(mycode));
81 for(int i = 0; i <= len1 ; i++){
82 int j = i;
83 int t = 0;
84 mycode[i].s = huff[i].s;
85 while(j < len2){
86 if(huff[huff[j].pr].lc == j)
87 mycode[i].co[t++] = '0';
88 else mycode[i].co[t++] = '1';
89 j = huff[j].pr ;
90 }
91 reserve(mycode[i].co);
92 cout << "the code of " << mycode[i].s
93 << " is " << mycode[i].co <<endl;
94 }
95 delete[] mycode;
96 }
97
98 int main(){
99 int len1 = input();
100 int len2 = createTree(len1);
101 coding(len1,len2);
102 }
103
104
105
106
is-programmer 2011-12-06 14:46 鍙戣〃璇勮
]]>