榪欎釜闂鐨勭畻娉曚笌Kruskal綆楁硶闈炲父鐩鎬技錛岄鍏堟瘡涓涓偣閮芥槸涓涓仛綾伙紝鐒跺悗渚濇鎸夌収Kruskal榪涜璁＄畻銆傘傘傜浉褰撲簬鍦↘ruskal涓垹闄や簡k-1鏉℃渶璐電殑杈廣?
2 鍋囪緇欏畾涓涓繛閫氬浘G錛屽亣瀹氳竟鐨勮垂鐢ㄩ兘鏄笉鍚岀殑錛孏鏈塶涓《鐐瑰拰m鏉¤竟錛屾寚瀹氫簡G鐨勪竴鏉＄壒瀹氱殑杈筫錛岀粰鍑轟竴涓繍琛屾椂闂村湪O(m+n)鐨勭畻娉曟潵紜畾e鏄惁鍖呭惈鍦℅鐨勪竴媯墊渶灝忕敓鎴愭爲閲屻?
綆楁硶鐜板湪灝卞凡緇忓緢鏄劇劧浜嗭紝鎴戜滑閫氳繃浠嶨涓垹闄ゆ墍鏈夋潈姣攅澶х殑杈癸紝錛堝寘鎷琫錛夌劧鍚庝嬌鐢ㄧ湅涓涓媏涓殑涓や釜绔殑鏄惁鑱旈氥傚綋鍓嶄粎褰撴病鏈夎繖鏍蜂竴鏉¤礬寰勭殑鏃跺欙紝e灞炰簬涓媯墊渶灝忕敓鎴愭爲銆?
3 鐪嬩竴涓嬫渶灝忕敓鎴愭爲鐨勪袱涓ц川錛?#160;
鍓叉ц川錛氬綋e鏄粠鏌愪釜闆嗗悎S璺ㄥ埌琛ラ泦V-S鐨勬渶渚垮疁鐨勮竟錛岄偅涔堝畠鍦ㄦ瘡涓棰楁渶灝忕敓鎴愭爲閲屻?
鍦堟ц川錛氬鏋渆鏄煇涓湀C涓婃渶璐電殑杈癸紝閭ｄ箞瀹冧笉鍦ㄦ渶灝忕敓鎴愭爲閲屻?
4 涓涓鍚庨棶棰橈細
緇欏畾涓涓渶鐭礬闂錛屼絾鏄竟鏉冩槸涓涓埌杈炬椂闂寸殑鍑芥暟(杈規(guī)潈緇熶竴涓烘椂闂寸殑閲忕翰錛?鍑芥暟鍗曡皟閫掑)錛屾鏃朵粛鐒舵槸Dijkstra綆楁硶錛孌ijkstra 綆楁硶瀹炶川灝辨槸涓涓搴︿紭鍏堟悳绱€?
5 緇欏畾涓媯靛畬鍏ㄤ簩鍙夋爲錛岀劧鍚庢瘡涓竟鏈夋潈鍊箋傝姹備慨鏀硅竟錛岀劧鍚庝嬌寰楄窡鍒版瘡涓彾瀛愯妭鐐圭殑璺濈鐩稿悓錛岃姹備慨鏀圭殑鍜屾渶灝忥紵緇欏嚭涓涓畻娉曪紝榪欎釜鍦ㄧ數璺璁′腑灝辨槸鍚屾椂鎬х殑瑕佹眰銆?
榪欎釜鏄釜闈炲父涓嶉敊鐨勭畻娉曘傝繕鏄竴涓掑綊鐨勮繃紼嬶細
6
緇欏畾涓涓繛閫氬浘錛屼粬鐨勮竟鐨勮垂鐢ㄩ兘鏄笉鍚岀殑錛岃瘉鏄嶨鏈夊敮涓鐨勪竴媯墊渶灝忕敓鎴愭爲銆?
濡傛灉G鏈変袱媯墊渶灝忕敓鎴愭爲錛屽垯T 鍜孭錛屽繀鐒舵湁涓嶅悓鐨勮竟錛屾妸T涓嶱涓嶅悓鐨勮竟鍔犲叆鍒癙涓紝蹇呯劧褰㈡垚鍦堛?
]]>
1:
2: #include <queue>
3: #include <iostream>
4: #include <string.h>
5: #include <stdio.h>
6: #include <algorithm>
7: #include <vector>
8: using namespace std;
9: #define V 30010 // vertex
10: #define E 150010 // edge
11: #define INF 0x3F3F3F3F
12:
13: struct node
14: {
15: int v, w, next;
16: }pnt[E];
17:
18: int head[V];
19: int dis[V];
20: bool vis[V];
21: int cnt[V]; // the num of the operation of push to Quque. negatvie cycle.
22: int e = 0; // the index of the edge
23: int N ; // the num of the vertex.
24: int M ; // the num of edges
25: int src, sink;
26: int father[V];
27: int ru[V];
28: void addedge(int u, int v, int w)
29: {
30: pnt[e].v = v; pnt[e].w= w;
31: pnt[e].next = head[u]; head[u] = e++;
32: }
33: void SPFA_init()
34: {
35: e=0;
36: memset(head, -1,sizeof(head));
37: memset(vis, 0 ,sizeof(vis));
38: memset(cnt, 0 ,sizeof(cnt));
39: for(int i=0; i<=N; i++) dis[i] = -1; // MODIFIED
40: memset(father, -1, sizeof(father));
41: }
42: int SPFA()
43: {
44: queue<int> Q;
45: for(int i=1; i<=N; i++)
46: {
47: src = i;
48: if(ru[i] == 0)
49: {
50: Q.push(src); vis[src] = 1; dis[src] = 0; ++cnt[src];
51: }
52: }
53: while(!Q.empty())
54: {
55: int u = Q.front(); Q.pop(); vis[u] = 0;
56: for(int i=head[u]; i!=-1; i=pnt[i].next)
57: {
58: int v = pnt[i].v;
59: if( dis[v] < dis[u] + pnt[i].w ) // MODIFIED
60: {
61: dis[v] = dis[u] + pnt[i].w;
62: father[v] = u;
63: if(!vis[v]) { Q.push(v); vis[v] = 1;}
64: if( ++cnt[v] > N) return -1; // positive cycle.
65: }
66: }
67: }
68: if(dis[sink] == -1 ) return -2; // can't from src to sink.
69: return dis[sink];
70: }
71:
72: int main()
73: {
74: //freopen("1078.txt","r",stdin);
75: scanf("%d", &N);
76: int a, b;
77: vector<pair<int, int> > C;
78: memset(ru, 0 ,sizeof(ru));
79: SPFA_init();
80: for(int i=0; i<N; i++)
81: {
82: int a, b;
83: scanf("%d%d", &a, &b);
84: C.push_back(make_pair(a,b));
85: for(int i=0; i<C.size(); i++)
86: {
87: if(a<C[i].first && b> C[i].second)
88: {
89: ru[C.size()]++;
90: addedge(i+1,C.size() , 1);
91: }
92: else if(a> C[i].first && b< C[i].second)
93: {
94: ru[i+1]++;
95: addedge(C.size(), i+1,1);
96: }
97: }
98: }
99: SPFA();
100: //for(int i=1; i<=N; i++) cout<<father[i]<<" "; cout<<endl;
101: int ret =0; int idx = -1;
102: for(int i=1; i<=N; i++)
103: {
104: if(dis[i]>ret)
105: {
106: ret = dis[i];
107: idx = i;
108: }
109: }
110: if(ret == 0)
111: {
112: cout<<1<<endl;
113: cout<<1<<endl;
114: }
115: else
116: {
117: cout<<ret+1<<endl;
118: vector<int> D;
119: D.push_back(idx);
120: while(father[idx] != -1)
121: {
122: D.push_back(father[idx]);
123: idx = father[idx];
124: }
125: reverse(D.begin(), D.end());
126: for(int i=0; i<D.size(); i++) cout<<D[i]<<" ";
127: cout<<endl;
128: }
129: return 0;
130: }
]]>
http://acm.timus.ru/problem.aspx?space=1&num=1078
1:
2: #include <queue>
3: #include <iostream>
4: #include <string.h>
5: #include <stdio.h>
6: using namespace std;
7: #define V 505 // vertex
8: #define INF 0x3F3F3F3F
9: int N;
10: int dis[V][V];
11: int path[V][V];
12:
13: // normal distance.
14: void floyd()
15: {
16: for(int k=1;k<=N;k++)
17: {
18: for(int i=1;i<=N;i++)
19: {
20: for(int j=1;j<=N;j++)
21: {
22: if(dis[i][k]== -INF || dis[k][j] == -INF) continue;
23: if(dis[i][k] + dis[k][j] > dis[i][j])
24: {
25: dis[i][j] = dis[i][k] + dis[k][j];
26: path[i][j] = path[i][k];
27: }
28:
29: }
30: }
31: }
32: }
33: void floyd_path(int i, int j)
34: {
35: int k=path[i][j];
36: while(k!=j)
37: {
38: printf(" %d", k );
39: k= path[k][j];
40: }
41: }
42:
43: int main()
44: {
45: //freopen("1078.txt","r",stdin);
46: scanf("%d", &N);
47: int a, b;
48: vector<pair<int, int> > C;
49: memset(dis, 0 ,sizeof(dis));
50: for(int i=0; i<N; i++)
51: {
52: scanf("%d%d", &a, &b);
53: C.push_back(make_pair(a,b));
54: for(int i=0; i<C.size(); i++)
55: {
56: if(a<C[i].first && b> C[i].second)
57: {
58: dis[i+1][C.size()] = 1;
59: path[i+1][C.size()] = C.size();
60: }
61: else if(a> C[i].first && b< C[i].second)
62: {
63: dis[C.size()][i+1]=1;
64: path[C.size()][i+1] = i+1;
65: }
66: }
67: }
68: for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(dis[i][j]==0) dis[i][j]=-INF;
69: floyd();
70: int ret = 0;
71: for(int i=1; i<=N; i++)
72: {
73: for(int j=1; j<=N; j++)
74: {
75: if(dis[i][j] > ret)
76: {
77: ret = dis[i][j];
78: a = i; b = j;
79: }
80: }
81: }
82: if(ret == 0)
83: {
84: cout<<1<<endl;
85: cout<<1<<endl;
86: }else
87: {
88: cout<<ret+1<<endl;
89: cout<<a;
90: floyd_path(a,b);
91: cout<<" "<<b<<endl;
92: }
93: return 0;
94: }
95:
]]>
1:
2: #include <iostream>
3: #include <vector>
4: #include <algorithm>
5: #include <queue>
6: #include <string.h>
7: #include <stdio.h>
8: using namespace std;
9:
10: #define V 1005
11: #define E 100005
12: #define INF 329999
13:
14: // v :the end point of an edge. w : the weight of the weight next:cluster according to the begin point of the edge
15: struct node
16: {
17: int v, w,next;
18: node(int vv=0, int ww=0):v(vv),w(ww){}
19: bool operator < (const node& r) const{return w> r.w;}
20: }pnt[E],pnt1[E];
21:
22: int e=0,N,M,s;
23:
24: int head[V];
25: int dis[V];
26: bool vis[V];
27: int src, sink;
28:
29: void Dijkstra()
30: {
31: priority_queue<node> Q;
32: vis[src] = 1; dis[src] = 0;
33: Q.push(node(src, 0));
34: for (int u = src, i=1; i< N; i++)
35: {
36: for (int j = head[u]; j != -1; j = pnt[j].next) // j is edge number.
37: {
38: int v = pnt[j].v;
39: if (vis[v] == 0 && dis[v] > dis[u] + pnt[j].w )// pre is the current vertex
40: {
41: dis[v] = dis[u] + pnt[j].w;
42: Q.push(node(v, dis[v]));
43: }
44: }
45: while (!Q.empty() && vis[Q.top().v]) Q.pop();
46: if (Q.empty()) break;
47: vis[u = Q.top().v] = 1; Q.pop();
48: }
49: }
50: int head1[V];
51: inline void addedge1(int u, int v, int w)
52: {
53: pnt1[s].v =v; pnt1[s].w = w; pnt1[s].next = head1[u]; head1[u]=s++;
54: }
55: inline void addedge(int u, int v, int w){
56: pnt[e].v = v; pnt[e].w = w; pnt[e].next= head[u]; head[u]=e++;
57: }
58:
59: void Dijkstra_init()
60: {
61: e = 0; s =0;
62: memset(head, -1, sizeof(head));
63: memset(head1, -1, sizeof(head));
64: memset(vis, 0, sizeof(vis));
65: scanf("%d%d", &N , &M);
66: for (int i = 0; i <=N; i++) dis[i] = INF;
67: scanf("%d", &src);
68: //cout<<src<<endl;
69: for(int i=0; i<M; i++)
70: {
71: int a, b, c;
72: scanf("%d%d%d", &a, &b, &c);
73: addedge(a, b, c);
74: addedge1(b,a, c);
75: }
76:
77:
78: }
79:
80: int main()
81: {
82: //freopen("3268.txt","r",stdin);
83:
84: Dijkstra_init();
85: Dijkstra();
86: int dis1[V];
87: for(int i=0; i<=N; i++) dis1[i] = dis[i];
88: //for(int i=1; i<=N; i++) cout<<dis[i]<<" "; cout<<endl;
89: memset(vis, 0 ,sizeof(vis));
90: for(int i=0; i<=N; i++) { dis[i]= INF; head[i] = head1[i];}
91: for(int i=0; i<M; i++)
92: {
93: pnt[i]=pnt1[i];
94:
95: }
96: Dijkstra();
97: //for(int i=1; i<=N; i++) cout<<dis[i]<<" "; cout<<endl;
98: int ret = 0;
99: for(int i=1; i<=N; i++) ret = max(ret, dis1[i]+dis[i]);
100: cout<<ret<<endl;
101: return 0;
102: }
103:
]]>
1: /**
2: search the longest path , just jude whether there are a positve cycle.
3:
4: */
5:
6: #include <queue>
7: #include <iostream>
8: #include <string.h>
9: #include <stdio.h>
10: using namespace std;
11: #define V 3000 // vertex
12: #define E 1500 // edge
13: #define INF 1000000.0f
14:
15: struct node
16: {
17: int v, next;
18: double R,C,w;
19: }pnt[E];
20:
21: int head[V];
22: double dis[V];
23: bool vis[V];
24: int cnt[V]; // the num of the operation of push to Quque. negatvie cycle.
25: int e = 0; // the index of the edge
26: int N ; // the num of the vertex.
27: int M ; // the num of edges
28: int src, sink;
29: double val;
30: void addedge(int u, int v, double R, double C)
31: {
32: pnt[e].v = v; pnt[e].w= 0;
33: pnt[e].R = R; pnt[e].C = C;
34: pnt[e].next = head[u]; head[u] = e++;
35: }
36: void SPFA_init()
37: {
38: e=0;
39: memset(head, -1,sizeof(head));
40: memset(vis, 0 ,sizeof(vis));
41: memset(cnt, 0 ,sizeof(cnt));
42: for(int i=0; i<=N; i++) dis[i] = 0;
43: }
44: int SPFA()
45: {
46: queue<int> Q;
47: Q.push(src); vis[src] = 1; dis[src] = val; ++cnt[src];
48: while(!Q.empty())
49: {
50: int u = Q.front(); Q.pop(); vis[u] = 0;
51: for(int i=head[u]; i!=-1; i=pnt[i].next)
52: {
53: int v = pnt[i].v;
54: pnt[i].w = (dis[u] - pnt[i].C)*pnt[i].R - dis[u];
55: //cout<<u<<" to "<<v<<" "<<pnt[i].w<<endl;
56: if( dis[v] < dis[u] + pnt[i].w )
57: {
58: dis[v] = dis[u] + pnt[i].w;
59: //cout<<u<<" to "<<v<<" "<<pnt[i].w<<" "<<dis[v]<<endl;
60: if(!vis[v]) { Q.push(v); vis[v] = 1;}
61: if( ++cnt[v] > N) return -1; // negative cycle.
62: }
63: }
64: }
65: return 1;
66: //if(dis[sink] == INF) return -2; // can't from src to sink.
67: //return dis[sink];
68: }
69:
70: int main()
71: {
72: freopen("1860.txt","r",stdin);
73: scanf("%d%d", &N , &M);
74:
75: scanf("%d", &src);
76: //cout<<src<<endl;
77: scanf("%lf", &val);
78: //cout<<val<<endl;
79: SPFA_init();
80: for(int i=0; i<M; i++)
81: {
82: int a, b; double Rab, Cab, Rba,Cba;
83: scanf("%d%d", &a, &b);
84: scanf("%lf%lf", &Rab, &Cab);
85: scanf("%lf%lf", &Rba, &Cba);
86: addedge(a, b,Rab, Cab);
87: addedge(b,a,Rba, Cba);
88: //cout<<Rab<<" "<<Cab<<" "<<Rba<<" "<<Cba<<endl;
89: }
90: int ret = SPFA();
91: if(ret == -1) cout<<"YES"<<endl;
92: else cout<<"NO"<<endl;
93: return 0;
94: }
]]>
https://github.com/Sosi/ProgrammingContest/blob/master/OnlineJudge/POJ/PKU3169.cpp
1:
2: #include <queue>
3: #include <iostream>
4: #include <string.h>
5: #include <stdio.h>
6: using namespace std;
7: #define MAXN 1005 // vertex
8: #define MAXM 20005 // edge
9: #define INF 0x3F3F3F3F
10:
11: struct node
12: {
13: int v, w, next;
14: }pnt[MAXM];
15:
16: int head[MAXN];
17: int dis[MAXN];
18: bool vis[MAXN];
19: int cnt[MAXN]; // the number of the operation of push to Quque. negatvie cycle.
20: int num = 0; // the index of the edge
21: int N ; // the number of the vertex.
22: int M ; // the number of edges
23: int src, sink;
24: void addedge(int u, int v, int w)
25: {
26: pnt[num].v = v; pnt[num].w= w;
27: pnt[num].next = head[u]; head[u] = num++;
28: }
29:
30: int SPFA()
31: {
32: for(int i=0; i<=N; i++)
33: {
34: vis[i]=0; dis[i] = INF; cnt[i] = 0;
35: }
36:
37: queue<int> Q;
38: Q.push(src); vis[src] = 1; dis[src] = 0; ++cnt[src];
39: while(!Q.empty())
40: {
41: int u = Q.front(); Q.pop(); vis[u] = 0;
42: for(int i=head[u]; i!=-1; i=pnt[i].next)
43: {
44: int v = pnt[i].v;
45: if( dis[v] > dis[u] + pnt[i].w )
46: {
47: dis[v] = dis[u] + pnt[i].w;
48: if(!vis[v]) {Q.push(v); vis[v] = 1;}
49: if( ++cnt[v] > N) return -1; // negative cycle.
50: }
51: }
52: }
53: if(dis[sink] == INF) return -2; // can't from src to sink.
54: return dis[sink];
55: }
56:
57: int main()
58: {
59: int ml,md;
60: while(scanf("%d%d%d", &N , &ml, &md)!= EOF)
61: {
62: num = 0;
63: memset(head, -1, sizeof(head));
64: int a, b, c;
65: for(int i=0; i<ml; i++)
66: {
67: scanf("%d%d%d", &a, &b, &c);
68: if(a>b) swap(a,b);
69: addedge(a, b,c);
70: }
71: for(int i=0; i<md; i++)
72: {
73: scanf("%d%d%d", &a, &b, &c);
74: if(a<b) swap(a,b);
75: addedge(a, b, -c);
76: }
77: src = 1; sink = N;
78: printf("%d\n", SPFA());
79: }
80: return 0;
81: }
]]>
https://github.com/Sosi/ProgrammingContest/blob/master/OnlineJudge/POJ/PKU3159.cpp
1: #include <queue>
2: #include <iostream>
3: #include <string.h>
4: #include <stdio.h>
5: using namespace std;
6: #define MAXN 30010 // vertex
7: #define MAXM 150010 // edge
8: #define INF 0x3F3F3F3F
9:
10: struct node
11: {
12: int v, w, next;
13: }pnt[MAXM];
14:
15: int head[MAXN];
16: int dis[MAXN];
17: bool vis[MAXN];
18: int cnt[MAXN]; // the number of the operation of push to Quque. negatvie cycle.
19: int num = 0; // the index of the edge
20: int N ; // the number of the vertex.
21: int M ; // the number of edges
22: int src, sink;
23: void addedge(int u, int v, int w)
24: {
25: pnt[num].v = v; pnt[num].w= w;
26: pnt[num].next = head[u]; head[u] = num++;
27: }
28:
29: int SPFA()
30: {
31: for(int i=0; i<=N; i++)
32: {
33: vis[i]=0; dis[i] = INF; cnt[i] = 0;
34: }
35:
36: int Q[MAXM], top=1;
37: Q[0] = src; vis[src] = 1;
38: dis[src] = 0;
39: while(top)
40: {
41: int u = Q[--top]; vis[u] = 0;
42: for(int i = head[u]; i!=-1; i=pnt[i].next)
43: {
44: int v = pnt[i].v;
45: if(dis[v]> dis[u] + pnt[i].w )
46: {
47: dis[v]= dis[u] +pnt[i].w;
48: if(!vis[v])
49: {
50: Q[top++] = v; vis[v]= 1;
51: }
52: }
53:
54: }
55: }
56:
57:
58:
59: return dis[sink];
60: }
61:
62: int main()
63: {
64: //freopen("3159.txt", "r", stdin);
65: while(scanf("%d%d", &N , &M)!= EOF)
66: {
67: num = 0;
68: memset(head, -1, sizeof(head));
69: for(int i=0; i<M; i++)
70: {
71: int a, b, c;
72: scanf("%d%d%d", &a, &b, &c);
73: addedge(a, b,c);
74: }
75: //cout<<num<<endl;
76: src = 1; sink = N;
77: //cout<<"src "<<src<<" sink "<<N<<endl;
78: printf("%d\n", SPFA());
79: }
80: return 0;
81: }
]]>
浠?綰у崌鍒?綰э紝鏈?/3鐨勫彲鑳芥垚鍔燂紱1/3鐨勫彲鑳藉仠鐣欏師綰э紱1/3鐨勫彲鑳戒笅闄嶅埌0綰э紱
浠?綰у崌鍒?綰э紝鏈?/9鐨勫彲鑳芥垚鍔燂紱4/9鐨勫彲鑳藉仠鐣欏師綰э紱4/9鐨勫彲鑳戒笅闄嶅埌1綰с?
姣忔鍗囩駭瑕佽姳璐逛竴涓疂鐭籌紝涓嶇鎴愬姛榪樻槸鍋滅暀榪樻槸闄嶇駭銆?
姹傝嫳闆勪粠0綰у崌鍒?綰у鉤鍧囪姳璐圭殑瀹濈煶鏁扮洰銆?/p>
榪欎釜棰樼洰縐掓潃浜嗕竴澶х墖錛屼竴寮濮嬬湅鍒拌繖涓鐩紝绔嬪埢鍙嶅簲鍑烘潵鐨勬槸鑷姩鏈篋P錛岀劧鍚庡氨鏈濈潃鑷姩鏈篋P鍘繪兂錛屽緢蹇竴涓叕寮忓氨鍙互鎼炲嚭鏉ャ?/p>
dp[i][k]琛ㄧずk姝ヤ箣鍚庡湪i綰х殑姒傜巼銆?/p>
dp[0][k] = 1/3*dp[1][k-1];
dp[1][k] = dp[0][k-1]+1/3*dp[1][k-1] + 4/9*dp[2][k-1]
dp[2][k] = 1/3*dp[1][k-1] + 4/9* dp[2][k-1];
dp[3][k]= 1/9*dp[2][k-1];
鐒跺悗姝ら掓帹寮忓彲浠ュ啓鎴愮煩闃典箻娉曠殑褰㈠紡錛屾渶鍚庣殑緇撴灉灝辨槸姹?Sigma (k+1)/9*dp[2][k]; 榪欎釜鐭╅樀鍙互杞崲涓哄瑙掗樀錛岀劧鍚庡彲浠ユ眰鍑哄叾閫氶」鍏紡絳夌瓑銆傘傘傚叾瀹炶繖涓棶棰樻槸綰挎у樊鍒嗘柟紼嬬粍鐨勮В娉曘傘傘傝繕瑕佹眰鐗瑰緛鍊?+ Jordan鏍囧噯鍨媌ulalalalala銆傘傘傘傛垜瑙夊緱瑕佺畻鍑轟竴涓В鏋愯В鐨勮瘽鏋滄柇鏄藩浜嗐傘傘傜敤Matlab璺戜簡涓涓嬶細
A =
0 1/3 0
1 1/3 4/9
0 1/3 4/9
>> ret =0;
>> for k=1:1000
ret = ret+ (k+1)/9*[0 0 1]*A^k*[1 0 0]';
end
>> ret
ret =
30
绔熺劧鏄暣鏁?0.銆傘傝璧ゆ灉鏋滃緱閯欒鏅哄晢浜嗐傘傘?/p>
铔嬬柤鐨勭敤C++鍐嶈窇涓閬嶏細
#include <stdio.h> #include <iostream> using namespace std; double dp[4]; double nextdp[4]; int main() { for(int i=0; i<4; i++) dp[i]=0.0f; dp[0]=1.0f; double ret=0.0f; for(int i=0; i<100000000; i++) { for(int j=0; j<4; j++) nextdp[j]=0.0f; nextdp[0]= 1/3.0*dp[1]; nextdp[1]=1/3.0*dp[1]+dp[0]+4/9.0*dp[2]; nextdp[2]=4/9.0*dp[2]+1/3.0*dp[1]; nextdp[3]=1/9.0*dp[2]; ret+=i*dp[3]; for(int j=0; j<4; j++) dp[j]=nextdp[j]; if(i%1000000==0) { cout<<i<<" "; printf("%d %.4f\n",i, ret); } } return 0; }
榪樻槸30.銆傘?/p>
浜庢槸鎯沖埌鏈夋病鏈夌畝鍗曠殑鏂規(guī)硶銆傘傘傚叾瀹炲彲浠ヨ瀵熷埌褰撹秼浜庢棤絀風殑鏃跺欙紝姝ょ郴緇熺殑鏈熸湜鐨勬鐜囪漿縐繪槸瓚嬩簬紼沖畾鐨勶紒鍏跺疄浠諱綍緋葷粺鍦ㄦ棤絀鋒涔嬪悗錛岄兘鏄湡鏈涚ǔ瀹氱殑錛侊紒(搴熻瘽,浣嗗緢閲嶈錛?
鎵浠ワ紝浠? 鍒? 鎵闇瑕佺殑鏈熸湜姝ユ暟寰堢畝鍗曞氨鏄?. 浠?鍒?鐨勬湡鏈涙鏁板亣璁炬槸X 錛屽垯鍦ㄨ蛋浜嗕竴姝ヤ箣鍚庯紝鎴戜滑鍒嗘儏鍐佃璁烘墍澶勪綅緗傚彲浠ュ垪鍑?#160; X = 1+ 1/3*X + 1/3*(1+X) 鎵浠=4 ,浠? 閮? 鐨勬湡鏈涙鏁版槸4. 鍚岀悊錛屼粠2-3 X = 1+ 4/9*X + 4/9*(4+X) X =25. 浠?鍒?鐨勬湡鏈涙鏁版槸25. 鎵浠ヤ粠0鍒?鐨勬湡鏈涙鏁版槸 30.銆傘傘傘傘傘傘?/p>
鍧戠埞鍟婏紒錛侊紒錛侊紒錛侊紒錛侊紒錛侊紒錛?/p>
浣跨敤絎竴縐嶆濊礬鍙互姹傦紝闂鏄偅涓煩闃礎澶潙鐖廣傘傘傜湅鐪嬩粬鐨勭壒寰佸箋傘傘傘俥ig(A)
ans =
-1588/3201
1072/3461
457/474
榪樿甯︾潃n嬈℃柟鍘繪眰瑙p[2][k]鐨勯氶」銆傘傘傛潃浜嗘垜鍚с傘傜浜岀鏂規(guī)硶鏄В鍐寵繖綾婚棶棰樼殑涓囬噾娌瑰晩銆傚弽姝ｇ郴緇熻揪鍒扮ǔ鎬侊紝閭ｅ氨鐩存帴涓婄ǔ鎬佸叕寮忓惂銆傚叾瀹炴眰瑙ｅ樊鍒嗘柟紼嬬粍鐨勮В娉曚腑錛岄殣鍚嬌鐢ㄧ殑鏉′歡灝辨槸紼蟲佹柟紼嬨傘傘傛畩褰掑悓閫斿晩銆傘傘?/p>
緇欏畾涓涓嚫N鍙樺艦,鍙互璋冩暣浠繪剰澶氫釜欏剁偣,浣嗘槸璺濈鍙兘鏄? ,涓嶈兘璋冩暣涓や釜鐩擱偦鐨勯《鐐?姹傚彉鍖栦箣鍚庣殑澶氳竟褰㈢殑鏈澶у鍔犵殑闈㈢Н鏄灝?
榪欎釜闂鏄竴涓姩鎬佽鍒掗棶棰?涓轟簡浣塊棶棰樿兘澶熻揪鍒扮嚎鎬ц屼笉鏄渾褰㈠驚鐜殑,鎴戜滑闇瑕佽冭檻3涓儏鍐? 涓寮濮嬪啓浜嗕竴涓椽蹇冪殑鏋氫婦,浣嗚兘澶熸壘鍒板弽渚?
double dis(double x1, double y1, double x2, double y2) { return sqrt((x1-x2)*(x1-x2)+ (y1-y2)*(y1-y2)); } class PolyMove { public: double addedArea(vector <int> x, vector <int> y) { // It is a dynamic programming problem int n = x.size(); double ret = 0.0f; vector<double> best(n, 0.0); // first case best[0]=0.0f; best[1]=0.0f; for(int i=2; i<n; i++) best[i]= max(best[i-1], best[i-2]+ dis(x[i-2], y[i-2], x[i], y[i])*0.5f); ret = best[n-1]; //second case for(int i=0; i<n; i++) best[i]=0.0f; best[0]=0.0f; best[1]= dis(x[n-1], y[n-1], x[1],y[1])*0.5f; best[2]=best[1]; for(int i=3; i<n; i++) best[i]= max(best[i-1], best[i-2]+ dis(x[i-2], y[i-2], x[i], y[i])*0.5f); ret = max(best[n-1], ret); // third case<F5> for(int i=0; i<n; i++) best[i]=0.0f; best[0]= dis(x[n-2], y[n-2], x[0], y[0])*0.5f; best[1]=best[0]; for(int i=2; i<n-1; i++) best[i]= max(best[i-1], best[i-2]+ dis(x[i-2], y[i-2], x[i], y[i])*0.5f); ret = max(ret , best[n-2]); return ret; } };
]]>