Untitled

avatar
user_9278292
plain_text
a year ago
21 kB
12
Indexable
//
Đi ăn cưới

Do không trốn được Uranus nên Tomoky đành ngậm ngùi nhận thiệp và hôm nay là ngày cưới của Uranus, anh dậy từ rất sớm để đến công ty đón xe đi ăn cưới.

Đường đi từ công ty đến nhà anh Uranus được biểu diễn bằng 1 đồ thị.

Có N đỉnh được nối với nhau bằng M đường một chiều, các đỉnh đánh số từ 1 đến N. Giả sử công ty là đỉnh 1, nhà anh Uranus - nơi tổ chức đám cưới là đỉnh 2.

Do biết trên xe là team SPen, một team rất giỏi STC ở SVMC nên bác lái xe vui tính muốn đố mọi người tìm đường đi để đi từ công ty đến đám cưới rồi quay về công ty sao cho đường đi thỏa mãn mà số các đỉnh khác nhau phải đi qua là tối thiểu.

Hãy viết chương trình giúp bác lái xe tìm đường đi trên.

Input

Dòng đầu tiên chứa số bộ test T. Sau đó là T bộ test, mỗi bộ test có dạng:

*Dòng 1: Số tự nhiên N và M (N<=20).

*Dòng 2..1+M: Mỗi dòng chứa 2 số nguyên khác nhau A và B (1<=A,B<=N) – biểu diễn đường đi một chiều giữa hai đỉnh A và B. Không có hai đường đi một chiều nào trùng nhau.

Output

Mỗi bộ test in trên một dòng là số đỉnh khác nhau tối thiểu phải đi qua khi đi từ đỉnh 1 đến đỉnh 2 rồi quay về 1.

Example

Input:

2

6 7

1 3

3 4

4 5

5 1

4 2

2 6

6 3

9 11

1 3

3 4

4 2

2 5

5 3

3 6

6 1

2 7

7 8

8 9

9 1

Output:

6

6

#include <iostream>
using namespace std;
int n,m;
int a[21][20];
int vis[21];
int dem[21];
int kq,sum;

void backtrack(int k){
	if(vis[2]!=1&&vis[k]==2) return;
	if(vis[1]!=2&&vis[k]==3) return;
	if(vis[1]>=2&&vis[2]==1){
		if(kq>sum) kq=sum;
		return;
	}
	if(sum>=kq) return;
	for(int i=0; i<dem[k]; i++){
		vis[a[k][i]]++;
		if(vis[a[k][i]]==1) sum++;
		backtrack(a[k][i]);
		vis[a[k][i]]--;
		if(vis[a[k][i]]==0) sum--;
	}
}
int main(){
	//freopen("input.txt","r",stdin);
	int t;
	cin>>t;
	for (int tc=1; tc<=t;tc++){
		cin>>n>>m;
		for(int i=0; i<n; i++){
			dem[i]=0;
			vis[i]=0;
		}
		int x,y;
		for(int i=0; i<m; i++){
			cin>>x>>y;
			a[x][dem[x]]=y;
			dem[x]++;
		}
		kq=10000;
		sum=0;
		vis[1]=1;
		backtrack(1);
		cout<<kq+1<<endl;
	}
	return 0;
}
////
Hệ thống điện

Sau khi anh VenG đã xây dựng đường đi giữa những hòn đảo, anh Eagle được cử sang để xây dựng hệ thống điện giữa các hòn đảo cho người dân, do muốn ăn bớt kinh phí nên anh Eagle không xây dựng trạm phát điện trên tất cả các đảo mà chỉ xây trên 1 số đảo nhất định. Các đảo kết nối với nhau thành 1 mạng lưới điện. Rõ ràng những đảo nào ở càng xa nguồn phát thì điện sẽ càng yếu.

Để đảm bảo người dân không than phiền điện yếu, nên anh Eagle muốn tính toán xem điện ở đảo nào sẽ yếu nhất.

Độ yếu của điện tại đảo X được tính bằng 0 nếu đảo đó có trạm phát điện, nếu đảo X có kết nối điện với đảo Y mà đảo Y ở gần trạm phát hơn, độ yếu tại đảo X = độ yếu tại đảo Y + 1. Nếu đảo X không có điện thì có độ yếu bằng vô cùng (infinity).

Input

Dòng đầu tiên chứa số testcase T.

Mỗi test case gồm:

Dòng đầu tiên gồm 3 số nguyên N, M, H lần lượt là số đảo, M là số đảo có trạm phát điện, H là số kết nối 2 chiều. (N, M <= 1 000, H <= 10 000).

Dòng tiếp theo gồm M số là ID các đảo có máy phát điện (ID đánh số từ 0 tới N-1).

H dòng tiếp theo, mỗi dòng gồm 2 số u, v, cho biết đảo u có kết nối với đảo v.

 

Output

In ra đảo độ yếu của điện là cao nhất. Nếu có nhiều đáp án, in ra đảo có ID nhỏ nhất.

Example

Input:

2

6 3 5

0 5 2

0 1

1 2

4 5

3 5

0 2

6 2 3

5 2

0 5

0 1

3 4

 

Output:

 

1

3

#include <iostream>
using namespace std;
int qx[1000000];
int qy[1000000];
int f,r;
int vis[1001];
int n,m,h; 
int a[1001][1001];

void push(int x){
	r++;
	qx[r]=x;
	//qy[r]=y;
}

void pop(int &x){
	f++;
	x=qx[f];
	//y=qy[f];
}

int main(){
	//freopen("input.txt","r",stdin);
	int t;
	cin>>t;
	for (int tc=1; tc<=t;tc++){
		f=r=-1;
		//cout<<"#"<<tc<<" ";
		
		cin>>n>>m>>h;
		for(int i=0; i<n; i++){
			vis[i]=1000000;
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				a[i][j]=0;
			}
		}
		int x;
		for(int i=0; i<m;i++){
			cin>>x;
			push(x);
			vis[x]=0;
		}
		int y,z;
		for(int i=0; i<h; i++){
			cin>>y>>z;
			a[y][z]=a[z][y]=1;
		}
		while(f!=r){
			pop(x);
			for(int i=0; i<n; i++){
				if(a[x][i]==1&&vis[x]+1<vis[i]){
					push(i);
					vis[i]=vis[x]+1;
				}
			}
		}
		int max=0;
		for(int i=0; i<n; i++){
			if(max<vis[i]) max=vis[i];
		}
		for(int i=0; i<n; i++){
			if(max==vis[i]) {
				cout<<i<<endl;
				break;
			}
		}
	}
	return 0;
}
////
Phá hủy hệ thống điện

Sau khi biết tin Eagle xây dựng hệ thống điện và ăn bớt được rất nhiều kinh phí, VenG rất tức vì khi anh xây cầu anh đã không ăn bớt được đồng nào. Do đó anh quyết phá hệ thống điện của Eagle.

Do sợ bị phát hiện nên anh sẽ chỉ phá hệ thống điện ở trên 1 hòn đào, và anh muốn tìm hòn đảo nào sau khi phá xong thì hệ thống điện của Eagle bị chia cắt thành nhiều phần nhất.

Hãy giúp anh VenG tìm hòn đảo này.

Input:

Dòng đầu tiên ghi số bộ test, không lớn hơn 100.

Mỗi bộ test được tổ chức theo khuôn dạng sau:

 Dòng đầu tiên ghi lại số tự nhiên N không lớn hơn 100 là số hòn đảo.

Những dòng kế tiếp ghi lại ma trận biểu diễn hệ thong mạng lưới điện, trong đó 0 được hiểu là không có đường dây điện nối giữa điểm i và j, 1 được hiểu có đường dây điện trực tiếp giữa điểm i và điểm j (1<=i, j <= N).

Output

Với mỗi bộ test, in ra màn hình trên một dòng một số duy nhất là hòn đảo bị phá hủy hệ thống điện thỏa mãn yêu cầu bài toán (nếu có nhiều đảo cùng thỏa mãn yêu cầu thì in ra đảo có giá trị nhỏ nhất). Nếu không thể chia cắt được hệ thống điện, hãy in ra số 0.

Example

Input:

2

5

0 1 1 0 0

1 0 1 0 0

1 1 0 1 1

0 0 1 0 0

0 0 1 0 0

5

0 1 1 0 0

1 0 1 0 1

1 1 0 1 1

0 0 1 0 1

0 1 1 1 0

Output:

3

0
#include <iostream>
using namespace std;
int qx[1000000];
int qy[1000000];
int f,r;
int vis[100];
int n; 
int a[100][100];
int sovung[100];
void push(int x){
	r++;
	qx[r]=x;
	//qy[r]=y;
}

void pop(int &x){
	f++;
	x=qx[f];
	//y=qy[f];
}
int bfs(int x){
	for(int i=0; i<n; i++){
		vis[i]=0;
	}
	vis[x]=1;
	int dem=0;
	for(int i=0; i<n; i++){
		if(vis[i]==0){
			dem++;
			f=r=-1;
			int y=i;
			push(y);
			while(f!=r){
				pop(y);
				for(int j=0; j<n; j++){
					if(a[y][j]==1&&vis[j]==0){
						vis[j]=1;
						push(j);
					}
				}
			}
		}
	}
	return dem;
}
int main(){
	//freopen("input.txt","r",stdin);
	int t;
	cin>>t;
	for (int tc=1; tc<=t;tc++){
		//cout<<"#"<<tc<<" ";
		cin>>n;
		for(int i=0; i<n; i++){
			for(int j=0;j<n; j++){
				cin>>a[i][j];
			}
		}
		int max=0;
		for(int i=0; i<n; i++){
			sovung[i]=bfs(i);
			if(max<sovung[i]) max=sovung[i];
		}
		if(max==1) {
			cout<<"0"<<endl;
			continue;
		}
		for(int i=0; i<n; i++){
			if(max==sovung[i]) {
				cout<<i+1<<endl;
				break;
			}
		}
	}
	return 0;
}
///
Hugo về nhà
 

Hugo đang trền đường về nhà và cần đi qua 1 đoạn đường B.

Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng Hugo có 3 cách lựa chọn.

1. Pass

Trả số tiền quy định ở cổng đó để được đi qua

2. Hire

Trả gấp đôi số tiền ở cổng đó để thuê số binh sĩ gộp vào đoàn quân của mình

3. battle

Điều kiện để đánh nhau là số quân của Hugo >= số lượng lính tại cổng đó. Có các lưu ý:

+ Hugo k được tính vào số lượng của quân

+ Mỗi người lính chỉ tham gia được vào tối đa 3 trận đánh. Sau 3 trận đánh nếu đi nhóm binh sĩ đó còn sống thì cũng giải tán.

+ Mỗi trận đánh thì tất cả số binh sĩ đều tham gia.

+ Đánh nhau chết theo tỉ lệ 1: 1. Ai tham gia trước sẽ bị chết trước

Input:
Dòng đầu tiên là số lượng trường hợp thử nghiệm

Mỗi trường hợp thử nghiệm sẽ có
          Dòng đầu tiên chứa số lượng cổng N

          N dòng tiếp theo chứa 2 số là số binh lính và chi phí tại mỗi cổng

Output: In ra chi phí nhỏ nhất Hugo có thể đi qua đoạn đường B

Điều kiện input: số cổng <=20

-      2 <=Số lính và chi phí đi qua <=1000

VD:

Input
2

7

10 100

70 5

80 15

20 60

50 90

30 80

10 10

9

600 800

300 400

300 400

1000 400

300 600

100 300

600 300

600 500

1000 300

 

Output:

#1 150

#2 3000
#include <iostream>
using namespace std;
int cua[20][2];
int n;
int kq;
void backtrack(int k,int tien,int b0, int b1,int b2){
	if(tien>kq) return;
	if(k==n){
		if(kq>tien) kq=tien;
		return;
	}
	for(int i=0; i<3; i++){
		if(i==0){
			backtrack(k+1,tien+cua[k][1],b0,b1,b2);
		}
		if(i==1){
			backtrack(k+1,tien+2*cua[k][1],b0+cua[k][0],b1,b2);
		}
		if(i==2){
			if(b0+b1+b2<cua[k][0]) continue;
			if(cua[k][0]<=b2) backtrack(k+1,tien,0,b0,b1);
			else if(cua[k][0]>b2&&cua[k][0]<b1+b2) {
				backtrack(k+1,tien,0,b0,b1+b2-cua[k][0]);
			}
			else backtrack(k+1,tien,0,b0+b1+b2-cua[k][0],0);
		}
	}
}

int main(){
	//freopen("input.txt", "r", stdin);
	int t;
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		//cout<<"Case #"<<tc<<endl;
		cin>>n;
		
		for(int i=0; i<n; i++){
			cin>>cua[i][0]>>cua[i][1];
		}
		kq=10000000;
		backtrack(0,0,0,0,0);
		cout<<"#"<<tc<<" "<<kq<<endl;
	}
	return 0;
}
//// Graph
1.Chutrình(Userproblem)
Môtả
Chođồthịcóhướng,yêucầukiểmtrađồthịđócóchutrìnhhaykhông,nếucóchutrìnhinramộtchutrìnhbấtkìtheothứtựtăngdầncủachỉsốđỉnh.
Vídụ
Đồthịbêncó1chutrìnhlàB-C-E-D,nêntacầninratheothứtựtăngdầnlàBCDE.
Phântích
Đâylàbàitìmchutrìnhtrongđồthịcóhướng,việckiểmtra1đồthịcóchutrình
tacóthểsửdụngBFShoặcDFS,tuynhiênđểinrachutrìnhđótanênsửdụngDFS.
Hướnggiải
DFS
SửdụngthuậttoánduyệttrênđồthịDFS,nếutrongquátrìnhgọiDFStừđỉnhv,nếutagặp1đỉnhukềvới1đỉnhwmàđỉnhwđãđượcduyệtquakhigọiDFS(v)(wvàucùngđượcduyệttrong1lầnduyệttừv)thìtacó1chutrìnhbắtđầutừwvàkếtthúctạiu(w->…->u->w).
Đểphânbiệt2trườnghợpđỉnhwđãđượcduyệt(Case1và2ởhìnhbên),tasửdụng2giátrịđểphânbiệtcácđỉnhđãđượcduyệt:đỉnhđangởtrongstackvàđỉnhđãpoprakhỏistack.
CustomizedDFS
intA[1000],B[1000];//dataofGraph
intcolor[101];//0:notvisit,1:incallstack,2:popedoutstack
intChild[101];//additionaldata:keeptrackofcycle
intfound;//additionaldata:flagforcycledetection
voidDFS(intv){
color[v]=1;//Markvertexinstack
for(inti=0;i<M;i++){
if(found)//Exitcondition:meetvisitedvertex
break;
if(A[i]==v){
if(color[B[i]]==0){//vertexisnotvisited
Child[v]=B[i];//saveroute
DFS(B[i]);//insertneighboringelement
}
elseif(color[B[i]]==1){//meetvisitedvertex
found=B[i];
Child[v]=B[i];//saveroute
}
//ifcolor==2:noaction
}
}
color[v]=2;//Markvertexpopedoutstack
}

5. Sea and Island (User problem)
Môtả
ChomảngnhịphânkíchthướcNxN(2≤N≤500)môtảbốtrícủavùngbiểnvàđảo.Hãytìmtổngsốlượngvùngnước(0)vàvùngđảo(1)trongsơđồ.
Thờigian:1giâycho20phépthử.
Phântích
Cóthểsửdụngqueueđểduyệttoànbộvùng0hoặc1khigặp1phầntửcủavùngđó
Hướnggiải
VétcạnsửdụngBFS/DFS
•Duyệtquatoànbộmatrận,nếugặpphầntửchưađượcduyệtthìtăngsốlượngvùngvàbắtđầuduyệttừphầntửđónhằmđánhdấutấtcảcácphầntửthuộccùng1vùng


6. Chiađôiđồthị(User problem)
Môtả
Cho đồthịvôhướngN đỉnh(5 ≤ N≤ 1000), hãychiađồthịthành2 nhómriêngbiệtsaocho: khôngcókếtnốigiữa2 đỉnhbấtkztrongcùng1 nhóm.
In racácđỉnhcủa1 trong2 nhómsaukhiphânchia. Nếukhôngthểphânchia, trảvề-1.
Vídụ
Vớiđồthịnhưhìnhvẽbên, nhóm1 baogồmcácđỉnh8-1-7-3. Đỉnh6 cóthểxếpvàonhóm1 hoặc2 đềuthỏamãn. Cóthểin rakếtquảlànhóm2 (4-5-9-2-6).
Phântích
BàitoáncóthểsửdụngDFShoặcBFSđểthựchiệnviệcduyệtđồthị. Trongquátrìnhduyệt, 2 đỉnhliềnkềnhausẽđượcđánhdấuvào2 nhómkhácnhau.
Nếugặplạiđỉnhđãđượcđánhdấuvàcùngnhómthìđồthịlàkhôngthểphânchia.
Note: đồthịcóthểkhôngliênthông(baogồmnhiềuđồthịcon) nêncầnlưuý điềukiệnđểduyệthếtđồthị.
7.Thànhphốtrọngyếu(Userproblem)
Môtả
ChođồthịliênthôngvôhướngNđỉnh(5≤N≤50)biểudiễnsơđồcácthànhphố,hãytìm1thànhphốmàkhixóabỏ,đồthịsẽmấtliênthông.Hãyinratấtcảcácthànhphốtrọngyếutrongđồthị.Nếukhôngcóthànhphốtrọngyếunào,trảvề-1.
Vídụ
Vớiđồthịnhưhìnhvẽbên,cócácthànhphốtrọngyếunhư1,2,7và8.
Phântích
Bàitoáncóthểgiảiquyếtbằngcáchvétcạn:thửngắtbỏ1thànhphốbấtkzsauđósửdụngDFShoặcBFSđểkiểmtratínhliênthôngcủađồthịsaukhiđãbỏđithànhphốđãchọn

9.Thốngtrịkhuvực(Userproblem)
Môtả
ChomatrậnNxN(5≤N≤100)chứacácphầntửcógiátrị0–5môtảlãnhthổ6vươngquốc.Yêucầusápnhậpcácvùngsố0vềcáclãnhthổkhácsaochovùngđồngnhấtcódiệntíchlớnnhất(cácvùngđượcchuyểnđổitrướckhôngđượctínhvàodiệntíchđểquyếtđịnhcácvùngchuyểnđổisau),sauđótrảvềsốlượngvùngcònlạisaukhisápnhập.
Phântích
CóthểsửdụngBFS/DFSđểduyệttoànbộvùng0vàtínhtoándiệntíchcácvùnglâncậnđểchuyểnđổi,sauđóduyệtlại1lầnđểđếmsốlượngvùng.
Hướnggiải
VétcạnsửdụngBFS/DFS
•Duyệtquatoànbộmatrận,nếugặpphầntửchưađượcduyệtthìbắtđầuduyệttừphầntửđó
•Cầnduyệt2lượt:1lượtnhằmconvertcácphầntử0và1lượtnhằmđếmsốlượngvùng
•Độphứctạp:O(N2)

10.InspectionbyRobot(Userproblem)
Môtả
ChomêcungđượcxâydựngbởiNxMhộphìnhvuôngkíchthước1x1.Mỗihộpsẽgồm0–4cửatheocáchướngtrên-dưới-trái-phải(16dạng).ChotọađộcủarobothỏisauKgiâysốlượngômàconrobotđócóthểdichuyểntớilàbaonhiêu,biếtthờigiandichuyểngiữa2hộp(nếuhaihộpđócóthểdichuyểntrựctiếpvớinhau)là1giây.
Vídụ
Trongvídụbên,nếurobotởvịtrí(3,2)sau1giâysốômàrobotcóthểđitớiđượclà4(ô(2,2),(3,2),(3,3)và(4,2)).
Phântích
ĐâylàbàitấtcảcácđỉnhcókhoảngcáchnhỏhơnhoặcbằngKtới1điểmchotrước.
Hướnggiải
BFS
SửdụngthuậttoánduyệtBFSđểtìmkhoảngcáchtừrobotđếncácôcònlại,trongquátrìnhduyệtsẽlưutrữgiátrịkhoảngcáchđếnôbắtđầu.ĐiềukiệndừngduyệtlàkhikhoảngcáchtừôhiệntạitớiôbắtđầubằngK.
Điểmkhócủabàitoánlàkiểmtra2ôcạnhnhaucóliênthôngvớinhauhaykhông?
→Thamkhảocáccáchtriểnkhaihàmconnect()tạislidesau.


// //backtrack
8.Airfare(SotongPractice)
Môtả
TìmcáchdichuyểntừcôngtyđiquaN(N<=12)thànhphố,mỗithànhphốchỉqua1lầnvàquaytrởlạicôngtyvớitổngchiphínhỏnhất.
Vídụ
Vớivídụbên,đườngđingắnnhấtđitừ1quacácđỉnhcònlạivàquaylạiđỉnh1là
1->3->2->5->4->1,vớitổngchiphílà30.
Phântích
ĐườngđicầntìmchínhlàmộthoánvịcủadãyNsốtừ1->N.
Hướnggiải
Quaylui
SửdụngkĩthuậtquayluiđểsinhracáchoánvịcủaNsốvớiđiềukiệnquayluikhiđangthửchènthànhphốthứKvàohoánvịlà:
•KhôngđóđườngđitừthànhphốthứK-1tronghoánvịđếnthànhphốthứK,
•Tổngchiphítừthànhphốthứ1đếnthànhphốthứKtronghoánvịđangsinhlớnhơnhoặcbằngtổngchiphínhỏnhấtđãtìmđược.

ĐộphứctạptínhtoánO(N!).

9.Painting(SotongTopCoder–Round3)
Môtả
Chođồthị,đếmtấtcảcáccáchtômàuđồthịcóVđỉnh(V<=30)vớitốiđa4màusaocho2đỉnhkềnhauphảikhácmàu.
Vídụ
Vớivídụbênlàmộtcáchtôchỉdùng3màuvàcótấtcả264cáchtôdùngtốiđa4màuthỏamãnkhôngcó2đỉnhkềnàocùngmàu.
Phântích
Mỗiđỉnhsẽcó4cáchtômàu,đồthịcóVđỉnhsẽcó4Vcáchtômàu,tuynhiêntrongnhữngcáchđósẽtồntạinhữngcáchmàkhôngthỏamãnđiềukiện2đỉnhkềnhauphảikhácmàu.
Hướnggiải
Quaylui
Sửdụngkĩthuậtquayluiđểthửtômàucácđỉnhtừlầnlượttừ1->Vbằng4cáchtômàuchomỗiđỉnh.NếutakhôngthểtiếptụctômàuchođỉnhthứK(khôngthỏamãnđiềukiện)thìsẽ“quaylui”đểthửcáchtômàukhácmàkhôngcầnphảithửtômàuchocácđỉnhtừK+1->Vchotrườnghợpđó.
ĐộphứctạptínhtoánO(4V).

10.Crossingariverwithcannibals(SotongPractice)
Môtả
BàitoánđưaNngườivàNquỷquasôngvớichiếcthuyềnlàcósứcchứalàM,saochongườikhôngbịquỷănthịtvớisốlầndichuyểnítnhất(ngườisẽbịquỷănthịtnếunhưnhómgồmngườivàquỷmàsốlượngquỷnhiềuhơnsốlượngngười).
Vídụ
VớivídụN=2vàM=2,cáchdichuyểnvớisốlầnítnhấtlà5nhưhìnhbên.
Phântích
•Phảidichuyểnluânphiênnhautứclàvừadichuyểnsangphảithìphảiquaylạitráiđểđónlượttiếptheo.
•Kếtthúcviệcchuyểnkhihếtsốngườivàquỷởbêntrái.

Hướnggiải
Quaylui
Sửdụngkĩthuậtquayluiđểsinhratấtcảcáccáchdichuyểncóthể,vớiđiềukiệnquayluilà:
•Bêntráicóngườivàsốngườiíthơnsốquỷ,
•Bênphảicóngườivàsốngườiíthơnsốquỷ,
•Lặplạitrườnghợpđãxétrồi.

11.Gamenhậpvai
Môtả
Trong1gamenhậpvai,bạnphảivượtquađoạnđườnggồmN(N<=20)chốtchặncủađịch,mỗichốtchặnsẽgồmKquânđịch,đểvượtquamỗichốtnàybạncó3cách:
1.DùngCtiềnđểđượcđiquachốtđó.
2.Sửdụng2*CtiềnđểKquânđịchởchốtđótrởthànhlínhcủamình.
3.Sửdụnglínhmìnhcóđểđánhquânđịch.

Điềukiệnđểcóthểdùnglínhđánhquânđịchlà:
•Sốlínhmìnhcóphảinhiềuhơnhoặcbằngsốquânđịchởchốtđó.
•Mộtnhómlính(đượcchiêumộởcáctrạmliêntiếp)chỉđượcthamgiatốiđa3trậnđánh.
•Sốlượnglínhbịgiảmsautrậnđánhbằngsốlượngquânđịch.
•Nhữnglínhnàođượcchiêumộtrướcsẽthamgiađánhtrước(bịgiếttrước).

Hãytìmcáchdichuyểnđểquađượcđoạnđườngvớitổngsốtiềnbỏralàítnhất.
Vídụ
Vớivídụcó7chốtđịchvớisốlượngquânđịchKvàchiphíCnhưhìnhbên.Tổngsốtiềnítnhấtphảibỏralà100+10+30+10=150.
Phântích
ChúngtacầnphảiquaNchốtchặn,mỗichốtcó3cáchchọnđểđi,nênđâythuộcdạngbàitoántổhợpcáccáchchọn.Sốcáchchọntốiđasẽlà3N,tuynhiênkhôngphảicáchchọnnàotrongsốtrêncũngthỏamãnđiềukiện.
Hướnggiải
Quaylui
Sửdụngkĩthuậtquayluiđểsinhracáctổhợpcáchchọn,mỗichốtsẽcó3trạngtháitươngứngvới3cáchchọn.
LưuýtrongcáchchọnchochốtthứK,kiểmtracóđủlínhchưathamgia3trậnđểđánhvớichốtthứKnàykhông.
ĐiềukiệnquayluiởđâylàkhisinhratrạngtháiđếnchốtthứK,màtổngchibỏralớnhơntổngchiphínhỏnhấtđãtìmđược,thìbỏquatrườnghợpnày.
Leave a Comment