cho.shDance Recital
Reorder the given routines so the total number of dancers shared by consecutive routines is as small as possible.
Medium6Dynamic programmingBit manipulationNo attempts yetTime limit1sMemory limit256 MBProblem
The production manager of a dance company has to work out the cost of the seasonal dance recital. Many of the dancers are good enough to perform in more than one routine, and that creates a problem. Each routine uses its own costume, so between routines a dancer has to report backstage to a wardrobe specialist, who changes the costume in time for the dancer's next routine.
A wardrobe specialist does a normal change when a dancer performs in two routines that are not next to each other. When a dancer performs in two consecutive routines, a quick change is needed instead. The wardrobe specialist charges one flat rate per recital that covers every normal change, and charges a very large amount for each quick change. The production manager has to keep the show under budget, and the order of the routines can be rearranged freely. Report the minimum number of quick changes needed for a given recital.
Each dancer in the recital is identified by one uppercase letter. There are never more than 26 dancers, so the letters A to Z are enough. A full recital is written as a list of routines, and each routine is written as a string of the dancers who appear in it. Consider this recital.
ABC
ABEF
DEF
ABCDE
FGH
It has 5 routines and 8 dancers, A through H. The first routine uses {A, B, C} and the second uses {A, B, E, F}. If those two routines are performed in that order, dancers A and B each need a quick change between them. Performing all five in the order written above needs six quick changes in total. The schedule can be rearranged like this.
ABEF
DEF
ABC
FGH
ABCDE
Now only two quick changes are needed, for E and F between the first two routines.
Input
The first line contains the number of routines R (2≤R≤10).
Each of the next R lines contains the cast of one routine. Every such line is a nonempty string of at most 26 non-repeating uppercase letters in lexicographic order. A dancer never appears twice in one routine, but a dancer may appear in many routines, and two or more routines may have identical casts.
Output
Print one integer, the minimum number of quick changes required for the recital.