Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 2088 | Accepted: 696 |
Description
Given a collection of N words, find an arrangement of the words that divides them among N lines, padding them with leading spaces to maximize the number of non-space characters that are the same as the character immediately above them on the preceding line. Your score for this game is that number.
Input
The first line of each set will be an integer N (1 <= N <= 10) giving the number of words in the test case. The following N lines will contain the words, one word per line. Each word will be made up of the characters 'a' to 'z' and will be between 1 and 10 characters long (inclusive).
End of input will be indicated by a non-positive value for N .
Output
Sample Input
5 abc bcd cde aaa bfcde 0
Sample Output
8
Hint
aaa
abc
bcd
cde
bfcde
Source
分析:状态压缩DP,把取单词的情况用二进制表示,容易得到状态转移方程
f[i][s|pow[i]]=max(f[i][s|pow[i]],f[j][s]+w[i][j]),其中 s为当前状态,,pow[i]=1<<(i-1);pow[i]&s==0,pow[j]&s>0,w[i][j]为单词i,j相邻的值
还是好挫地wrong了一次,最近实在是没状态啊~~~
找来一组数据:
10
abc
bc
abcd
bbc
bcd
dbc
a
bacd
ebdac
ac
答案:19
代码: