摘要: 求存在的最小價值的多重背包
閱讀全文
posted @
2012-03-12 20:16 Leo.W 閱讀(254) |
評論 (0) |
編輯 收藏
摘要: 水題一道，但讓我明白不必將所有結果（也不可能包括所有）算出來，只需要具體問題具體對待。
閱讀全文
posted @
2012-03-09 21:08 Leo.W 閱讀(254) |
評論 (0) |
編輯 收藏
摘要: 一道精彩的多重背包，思路不古板。適合初學者。
閱讀全文
posted @
2012-03-09 20:14 Leo.W 閱讀(317) |
評論 (0) |
編輯 收藏
摘要: 簡單貪心，但蘊含思想卻以小見大，可以舉一反三
閱讀全文
posted @
2012-03-08 19:05 Leo.W 閱讀(193) |
評論 (0) |
編輯 收藏 1 /*
2 Author: Leo.W
3 Descriptipn: 計算N^N結果的最左邊的數
4 How to Do: 數學題 由sum=N^N,兩邊對10取對數,log10(sum)=Nlog10(N),有sum=10^(Nlog10(N));
5 由于10的整數次冪首位均為1，則僅需考慮Nlog10(N)的結果的小數部分即可
6 */
7 #include <stdio.h>
8 #include <math.h>
9 int main(){
10 //freopen("in.txt","r",stdin);
11 int t;
12 __int64 num,sum2;
13 scanf("%d",&t);
14 while(t--){
15 scanf("%I64d",&num);
16 double sum1=num*log10(double(num));
17 sum2=(__int64)sum1;
18 sum1-=sum2;
19 num=(__int64)pow(10.0,sum1);
20 printf("%I64d\n",num);
21 }
22 return 0;
23 }
posted @
2012-03-08 18:56 Leo.W 閱讀(896) |
評論 (1) |
編輯 收藏
摘要: 完全背包問題
閱讀全文
posted @
2012-03-07 15:03 Leo.W 閱讀(557) |
評論 (3) |
編輯 收藏 1 /*
2 Author: Leo.W
3 Descriptipn:尋找質因數僅為2、3、5、7其中若干的正整數
4 How to Do: 動態規劃，由2、3、5、7開始依次疊増；
5 */
6 #include <stdio.h>
7 #include <string.h>
8 int num[5900];
9 inline int min(int a,int b){
10 if(a<b) return a;
11 return b;
12 }
13 int main(){
14 //freopen("in.txt","r",stdin);
15 int i,t=1,p2=1,p3=1,p5=1,p7=1;//表示當前遞增依次為2、3、5、7
16 char ch[5][3]={"th","st","nd","rd"};
17 for(i=1;i<=5842;i++){
18 num[i]=t;
19 t=min(min(num[p2]*2,num[p3]*3),min(num[p5]*5,num[p7]*7));
20 if(t==num[p2]*2)
21 p2++;
22 if(t==num[p3]*3)
23 p3++;
24 if(t==num[p5]*5)
25 p5++;
26 if(t==num[p7]*7)
27 p7++;
28 }
29 while(scanf("%d",&t),t){
30 i=0;
31 if(t%100!=11&&t%10==1)
32 i=1;
33 if(t%100!=12&&t%10==2)
34 i=2;
35 if(t%100!=13&&t%10==3)
36 i=3;
37 printf("The %d%s humble number is %d.\n",t,ch[i],num[t]);
38
39 }
40 return 0;
41 }
posted @
2012-03-07 14:55 Leo.W 閱讀(214) |
評論 (0) |
編輯 收藏 1 /*
2 Author: Leo.W
3 Descriptipn: 給定幾個頂點以及已知某幾個頂點存在通路，求最少還需幾條路即可完成連通圖
4 How to Do: 由最后一組測試數據易知999 0，且結合最小生成樹的知識可得，連通分量數減一即得解
5 */
6 #include <iostream>
7 #include <stdio.h>
8 #include <string.h>
9 using namespace std;
10 #define MAXSIZE 1000
11 int path[MAXSIZE][MAXSIZE];
12 bool appear[MAXSIZE];
13 bool chose[MAXSIZE];
14 int m,n,lt;//圖中連線后的連通分量數
15
16 void bfs(int num){
17 chose[num]=true;
18 int i;
19 for(i=1;i<=m;i++)
20 if(i!=num&&path[num][i]==0&&!chose[i]){//點i與點num有連線，并且點i還未被選入集合
21 lt--; bfs(i);
22 }
23 }
24 int main(){
25 //freopen("in.txt","r",stdin);
26 while(scanf("%d",&m),m){//城鎮數
27 scanf("%d",&n);//已有的公路條數
28 lt=m;
29 memset(appear,false,MAXSIZE);
30 memset(chose,false,MAXSIZE);
31 int i,j;
32 for(i=1;i<=m;i++){
33 for(j=1;j<=m;j++)
34 path[i][j]=MAXSIZE;
35 }
36 for(i=0;i<n;i++){
37 int begin,end;
38 scanf("%d%d",&begin,&end);
39 appear[begin]=appear[end]=true;//表示已經連上線的點,即已經出現
40 path[begin][end]=path[end][begin]=0;
41 }
42 for(i=1;i<=m;i++)
43 if(appear[i]&&!chose[i]){
44 bfs(i);
45 }
46 printf("%d\n",lt-1);
47 }
48 return 0;
49 }
posted @
2012-03-06 13:38 Leo.W 閱讀(142) |
評論 (0) |
編輯 收藏 1 /*
2 Author: Leo.W
3 Descriptipn: 給定幾個頂點以及各頂點間的距離，求連接所有頂點的所需的最短距離。
4 How to Do: 基礎的最小生成樹問題。易知此為稠密圖，故使用普里姆算法解題。
5 */ 6 #include <iostream>
7 #include <stdio.h>
8 #include <
string.h>
9 using namespace std;
10 11 #define MAXSIZE 100
12 int closePath[MAXSIZE];
13 int path[MAXSIZE][MAXSIZE];
14 bool chose[MAXSIZE];
15 int n;
//頂點數
16 17 int prim(
int a){
18 chose[a]=
true;
19 int i,sum=0,num=n-1,pos=a;
20 for(i=1;i<=n;i++) closePath[i]=path[a][i];
21 while(num){
22 int mins=10000000;
23 for(i=1;i<=n;i++){
24 if(!chose[i]&&closePath[i]<mins){
25 mins=closePath[i];
26 pos=i;
27 }
28 }
29 num--; sum+=mins;
30 chose[pos]=
true;
31 for(i=1;i<=n;i++){
32 if(!chose[i]&&closePath[i]>path[pos][i]){
33 closePath[i]=path[pos][i];
34 }
35 }
36 }
37 return sum;
38 }
39 int main(){
40 //freopen("in.txt","r",stdin);
41 while(scanf("%d",&n),n){
42 if(n==1) printf("0\n");
43 else{
44 memset(chose,
false,MAXSIZE);
45 int i,j,pathSum=n*(n-1)/2;
46 for(i=1;i<=n;i++){
47 for(j=1;j<=n;j++){
48 if(i==j) path[i][j]=0;
49 else path[i][j]=10000000;
50 }
51 }
52 for(i=1;i<=pathSum;i++){
53 int begin,end,len;
54 scanf("%d%d%d",&begin,&end,&len);
55 if(len<path[begin][end])
56 path[begin][end]=path[end][begin]=len;
57 }
58 printf("%d\n",prim(1));
59 }
60 }
61 return 0;
62 }
posted @
2012-03-05 18:30 Leo.W 閱讀(183) |
評論 (0) |
編輯 收藏 1 /*
2 Author: Leo.W
3 Descriptipn: 給定圖上的n個點及m條點間連線，試求從S點到W點的最短距離，若不存在，則輸出-1;
4 How to Do: 經典的最短路算法的應用，dijkstra算法自編寫
5 */ 6 #include <iostream>
7 using namespace std;
8 int n,m;
//點的個數，點間連線的條數
9 int path[205][1005];
10 bool node[205];
11 int Dijkstras(
int s,
int w){
12 int i,j;
13 node[s]=
true;
14 for(i=0;i<n;i++){
15 int mins=INT_MAX,pos=s;
16 for(j=0;j<n;j++){
//尋找為選入點的最小值
17 if(!node[j]&&mins>path[s][j]){
18 mins=path[s][j]; pos=j;
19 }
20 }
21 if(mins==INT_MAX||j>n)
break;
22 node[pos]=
true;
23 for(j=0;j<n;j++){
24 if(!node[j]&&path[pos][j]!=INT_MAX&&path[s][j]>path[s][pos]+path[pos][j]){
25 path[s][j]=path[s][pos]+path[pos][j];
26 path[j][s]=path[s][j];
27 }
28 }
29 }
30 return path[s][w];
31 }
32 int main(){
33 //freopen("in.txt","r",stdin);
34 while(scanf("%d%d",&n,&m)!=EOF){
35 int i,j;
36 for(i=0;i<n;i++){
37 node[i]=
false;
38 for(j=0;j<n;j++){
39 if(j==i) path[i][j]=0;
40 else path[i][j]=INT_MAX;
//表示兩點間無通路
41 }
42 }
43 for(i=0;i<m;i++){
44 int begin,end,len;
45 scanf("%d%d%d",&begin,&end,&len);
46 if(len<path[begin][end])
//此處是全題關鍵，WA了很久。。。?！緦忣}要細致啊】47 path[begin][end]=path[end][begin]=len;
//雙向賦值
48 }
49 int s,w;
50 scanf("%d%d",&s,&w);
51 if(s>w){
52 s=s^w;w=s^w;s=s^w;
53 }
54 if(s==w)
55 printf("0\n");
56 else{
57 int ans=Dijkstras(s,w);
58 if(ans==INT_MAX) printf("-1\n");
59 else printf("%d\n",ans);
60 }
61 }
62 return 0;
63 }
posted @
2012-03-04 12:30 Leo.W 閱讀(253) |
評論 (0) |
編輯 收藏