首页 > 代码库 > UVALive 7352 Dance Recital

UVALive 7352 Dance Recital

2024-08-16 21:00:46   210人阅读

 题意：

有n种舞蹈要跳 每种舞蹈需要每一行字符串所对应的那些人

如果一个人连着跳两个舞蹈 那么需要一个quick change

问需要的最少quick changes是多少

 

思路：

假期的题 又拿出来做一遍……

范围很感人10*26 这不暴力搜一发还等啥呢……

 

  1 /* ***********************************************  2 Author        :SunYuefeng  3 Created Time  :2016/10/16 20:17:34  4 File Name     :A.cpp  5 ************************************************ */  6   7 #include <stdio.h>  8 #include <string.h>  9 #include <iostream> 10 #include <algorithm> 11 #include <vector> 12 #include <queue> 13 #include <set> 14 #include <map> 15 #include <string> 16 #include <math.h> 17 #include <stdlib.h> 18 #include <time.h> 19 #define M(a,b) memset(a,b,sizeof(a)) 20 using namespace std; 21 const int maxn=27; 22 const int inf=0x3f3f3f3f; 23  24 int n,sum,ans; 25  26 char dance[15][maxn]; 27 int match[maxn][maxn]; 28 int way[15]; 29 bool vis[maxn]; 30  31  32 int solve(int x,int y){ //看两个舞蹈有几个人重复了 33     int sum=0; 34     int lenx=strlen(dance[x]); 35     int leny=strlen(dance[y]); 36     for(int i=0;i<lenx;i++) 37         for(int j=0;j<leny;j++) 38             sum+=(dance[x][i]==dance[y][j]); 39     return sum; 40 } 41  42 void dfs(int x){ //强行遍历 43     if(x>n){ 44         if(sum<ans) ans=sum; 45         return ; 46     } 47     for(int i=1;i<=n;i++){ //遍历部分 48         if(!vis[i]){ 49             way[x]=i; 50             vis[i]=true; 51             sum+=match[way[x-1]][i]; 52             dfs(x+1); 53             sum-=match[way[x-1]][i]; 54             vis[i]=false; 55         } 56     } 57 } 58  59 int main() 60 { 61     //freopen("in.txt","r",stdin); 62     //freopen("out.txt","w",stdout); 63     while(~scanf("%d",&n)){ 64         getchar(); 65         M(vis,false),M(match,0),M(way,0); 66         for(int i=1;i<=n;i++) 67             scanf("%s",dance[i]); 68         for(int i=1;i<=n;i++){ 69             for(int j=1;j<=n;j++){ 70                 if(i!=j) 71                     match[i][j]=match[j][i]=solve(i,j); //预处理匹配状况 72             } 73         } 74         ans=inf; //初始化ans sum 75         sum=0; 76         dfs(1); //搜索 77         printf("%d\n",ans); 78  79     } 80     return 0; 81 } 82 /* 83  84 5 85 ABC 86 ABEF 87 DEF 88 ABCDE 89 FGH 90 6 91 BDE 92 FGH 93 DEF 94 ABC 95 BDE 96 ABEF 97 4 98 XYZ 99 XYZ100 ABYZ101 Z102 103 104 */

 

UVALive 7352 Dance Recital


联系
我们