ACM Dance Recital 题解

 

题要求在所有表演的排列情况中， 找出换装次数最小的一种。 

考虑到题目数据规模比较小（n<=10, 10! = 3628800), 故可以暴力枚举所有的排列情况， 但有必要先将每两场表演所需换装的次数用二维数组记录下来， 否则可能会超时！

#include<bits/stdc++.h>
using namespace std;

int book[11][11];
int book2[11];
int book3[11];
int minn;
void dfs(int t, int n){
	if(t > n){
		int ans = 0;
		for(int i=1; i<=n-1; i++)
			ans += book[book2[i]][book2[i+1]];
		if(ans < minn) minn = ans;
		return;
	}
	for(int i=1; i<=n; i++){
		if(book3[i]==0){
			book2[t] = i;
			book3[i] = 1;
			dfs(t+1, n);
			book3[i] = 0;
		}
	}
}
int main(){
	int i,j,e,f,n,tmp;
	string s[30];
	cin>>n;
	for(i=1; i<=n; i++)
		cin>>s[i];
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++){
			tmp = 0;
			for(e=0; s[i][e]; e++)
				for(f=0; s[j][f]; f++)
					if(s[i][e] == s[j][f])
						tmp++;
			book[i][j] = tmp;
		}
	minn = INT_MAX;
	dfs(1, n);
	cout<<minn<<endl;
	return 0;
}