ACM Dance Recital(dfs+剪枝)

时间:2021-11-05 06:32:17

The Production Manager of a dance company has been tasked with determining the cost for the seasonal
dance recital. Because of their exceptional skills, many dancers will perform in more than one routine,
but this presents a problem; each dance routine incorporates a unique costume, so between routines,
dancers must report backstage to a Wardrobe Specialist, who can change the dancer’s costume in time
to begin their next scheduled routine.
A Wardrobe Specialist does a normal change on a dancer when the dancer performs in two routines
that are not consecutive, but when a dancer is required to perform in two consecutive routines, a quick
change is necessary. A Wardrobe Specialist charges a flat rate per recital that covers all normal changes,
but charges an exorbitant amount for each quick change. The Production Manager is responsible for
keeping the show under budget, and has hired you to write a program to report the minimum number
of quick changes needed for a given recital, given that the order of the dance routines could be changed.
To describe the cast of dancers that are to perform during a recital, each dancer is assigned an
identifying uppercase letter. (Fortunately, there are never more than 26 dancers, so characters from A
to Z suffice.) To describe a full recital, a list of individual routines is given, with a string of characters
defining which dancers appear in a routine. For example, consider the following recital description:
ABC
ABEF
DEF
ABCDE
FGH
The above list describes a recital with 5 dance routines, including a total of 8 individual performers
(dancers A through H). The first routine listed includes dancers {A, B, and C}. The second routine
includes dancers {A, B, E, and F}. Notice that if these first two routines are performed in the above
order, dancers A and B will require a quick change between the routines. In fact, if these five routines
are scheduled in the order given above, a total of six quick changes are required. However, the schedule
can be rearranged as follows:
ABEF
DEF
ABC
FGH
ABCDE
In this case, only two quick changes are required (those for E and F between the first two dances).
Input
The input file contains several test cases, each of them as described below.
The first line contains a single integer R, with 2 ≤ R ≤ 10, that indicates the number of routines
in the recital. Following that will be R additional lines, each describing the dancers for one routine in
the form of a nonempty string of up to 26 non-repeating, lexicographically sorted uppercase alphabetic
characters identifying the dancers who perform in that routine. Although a dancer’s letter will not
appear more than once in a single routine, that dancer may appear in many different routines, and it
may be that two or more routines have the identical set of dancers.ACM-ICPC Live Archive: 7352 – Dance Recital
2/2
Output
For each test case, output a single integer designating the minimum number of quick changes required
for the recital on a line by itself.
Sample Input
5
ABC
ABEF
DEF
ABCDE
FGH
6
BDE
FGH
DEF
ABC
BDE
ABEF
4
XYZ
XYZ
ABYZ
Z
Sample Output
2
3
4

题意:大概意思就是说给你n个字符数组,让你找出匹配度(相邻两个字符串之间相同元素的个数)最小的序列。

题解:由于n<=10,离线找出任意两个字符窜之间的匹配度,暴力dfs搜索+剪枝;如果在搜索的过程中sum>output(最小值,就不用继续搜了(剪枝);

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<string,string>pair1;
const int MAXN=1e3+;
int m,n,sum,output=MAXN;
int vis[MAXN];//标记数组
vector<string>str;
int ans[MAXN];//记录搜索的顺序
int mp[MAXN][MAXN];//第i个字符串和第j个字符串之间的匹配度
void ask_Qpoint()//求任意两个字符串之间的匹配度
{
for(int i=; i<m; i++)
{
for(int j=; j<m; j++)
{
int cnt=;
for(int k=,len=str[j].size(); k<len; k++)
{
if(str[i].find(str[j][k])!=string::npos)
{
cnt++;
}
}
mp[i][j]=cnt;
}
} }
void dfs(int depth,int sum)//depth表示深度,sum表示当前搜索过程中的最小值
{
if(sum>output||depth>=m)//剪枝
return ;
for(int i=,len=str.size(); i<len; i++)
{
if(!vis[i])
{
ans[depth]=i;
vis[i]=true;
if(depth>&&depth<m)
sum+=mp[ans[depth]][ans[depth-]];
if(depth<m-)
dfs(depth+,sum);
else{
output=min(output,sum);//比较最小值
sum=;
}
if(depth>&&depth<m)
sum-=mp[ans[depth]][ans[depth-]];
vis[i]=false;//标记还原
}
}
}
void init()//初始化
{
str.clear();
memset(mp,,sizeof(mp));
memset(vis,,sizeof(vis));
}
int main()
{
while(cin>>m)
{
init();
string arr;
output=MAXN;
for(int i=; i<m; i++)
{
cin>>arr;
str.push_back(arr);
}
ask_Qpoint();
dfs(,);
cout<<output<<endl; }
}

ACM Dance Recital(dfs+剪枝)的更多相关文章

  1. &ast;HDU1455 DFS剪枝

    Sticks Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Subm ...

  2. HDU 5952 Counting Cliques 【DFS&plus;剪枝】 (2016ACM&sol;ICPC亚洲区沈阳站)

    Counting Cliques Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) ...

  3. HDU 5937 Equation 【DFS&plus;剪枝】 (2016年中国大学生程序设计竞赛(杭州))

    Equation Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total S ...

  4. hdu 5887 Herbs Gathering (dfs&plus;剪枝 or 超大01背包)

    题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=5887 题解:这题一看像是背包但是显然背包容量太大了所以可以考虑用dfs+剪枝,贪心得到的不 ...

  5. POJ 3009 DFS&plus;剪枝

    POJ3009 DFS+剪枝 原题: Curling 2.0 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 16280 Acce ...

  6. poj 1724&colon;ROADS(DFS &plus; 剪枝)

    ROADS Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10777   Accepted: 3961 Descriptio ...

  7. DFS&lpar;剪枝&rpar; POJ 1011 Sticks

    题目传送门 /* 题意:若干小木棍,是由多条相同长度的长木棍分割而成,问最小的原来长木棍的长度: DFS剪枝:剪枝搜索的好题!TLE好几次,终于剪枝完全! 剪枝主要在4和5:4 相同长度的木棍不再搜索 ...

  8. DFS&plus;剪枝 HDOJ 5323 Solve this interesting problem

    题目传送门 /* 题意:告诉一个区间[L,R],问根节点的n是多少 DFS+剪枝:父亲节点有四种情况:[l, r + len],[l, r + len - 1],[l - len, r],[l - l ...

  9. LA 6476 Outpost Navigation (DFS&plus;剪枝)

    题目链接 Solution DFS+剪枝 对于一个走过点k,如果有必要再走一次,那么一定是走过k后在k点的最大弹药数增加了.否则一定没有必要再走. 记录经过每个点的最大弹药数,对dfs进行剪枝. #i ...

随机推荐

  1. python数字图像处理(9):直方图与均衡化

    在图像处理中,直方图是非常重要,也是非常有用的一个处理要素. 在skimage库中对直方图的处理,是放在exposure这个模块中. 1.计算直方图 函数:skimage.exposure.histo ...

  2. kindle 贴膜

    我自己贴膜也贴得很好.顺便和大家分享一下我的贴膜经验.需要的道具,一.抹布,二.一张银行卡,三.一卷小筒的透明胶.贴膜关键点,一.环境和贴面必须干净,二.用力要轻,三.顺序是从上往下.具体步骤:1.先 ...

  3. java中使用split分割字符串一个有趣的现象

    最近在项目中,发现了一个bug,充分了展示了自己对java底层的认知有很多的不足和欠缺. 下面有段代码: String str="1#2#3"; String[] strs=str ...

  4. socket头文件

    一. 三种类型的套接字:1.流式套接字(SOCKET_STREAM)    提供面向连接的可靠的数据传输服务.数据被看作是字节流,无长度限制.例如FTP协议就采用这种.2.数据报式套接字(SOCKET ...

  5. SQLSERVER 检查字段值域并输出行数和值列表

    select * from ( SELECT 'C_DILEI' as fen,'地类' as fcn, 'NVARCHAR'as ftype, '2'as flen, ( SELECT count( ...

  6. jquery层居中&comma;点击小图查看大图&comma;弹出层居中代码

    1.层居中 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w ...

  7. Rem &amp&semi; Viewport

    Rem布局 rem就是给根元素设置一个基准值 然后其他元素都以这个基准值作为单位 那么就可以在不同的手机上做出相同比例的元素了 事实上和百分比是同样的道理 网易和淘宝的rem 参考 http://ww ...

  8. java语言中的匿名类与lambda表达式介绍与总结 &lpar;Anonymous Classes and Lambda Expressions&rpar;

    2017/6/30 转载写明出处:http://www.cnblogs.com/daren-lin/p/anonymous-classes-and-lambda-expressions-in-java ...

  9. How to create DB2 user function easily by DB Query Analyzer 6&period;03

    How to create DB2user function easily by DB Query Analyzer 6.03 Ma Genfeng (Guangdong Unitoll Servic ...

  10. keepalived工作原理和配置文件说明

    keepalived是什么 keepalived是集群管理中保证集群高可用的一个服务软件,其功能类似于heartbeat,用来防止单点故障. keepalived工作原理 keepalived是以VR ...