hdu2817之状态压缩dp
时间：2014-04-03 06:02:42
收藏：0
阅读：463
WordStack
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3103 | Accepted: 1103 |
Description
As editor of a small-town newspaper, you know that a substantial number of your readers enjoy the daily word games that you publish, but that some are getting tired of the conventional crossword puzzles and word jumbles that you have been buying for years.
You decide to try your hand at devising a new puzzle of your own.
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.
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
Input data will consist of one or more test sets.
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 .
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
Your program should output a single line containing the maximum possible score for this test case, printed with no leading or trailing spaces.
Sample Input
5 abc bcd cde aaa bfcde 0
Sample Output
8
Hint
Note: One possible arrangement yielding this score is:
分析：可以事先求出num[i][j]表示字符串i和字符串j最多的相同位置相同字符个数，对于求i,j的num[i][j]可以i前后移动比较，i前移动相当于j后移，i后移就是在字符串前面加空格
aaa abc bcd cde bfcde
然后就是n个字符串怎么排列达到最大值了，由于n很小并且涉及到排列顺序，所以可以用状态压缩dp来求,状压的作用是去重复,既选取了相同的字符串只需要保存最大值
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;
const int MAX=(1<<10)+10;
int n;
int dp[MAX][20];
int num[20][20];
char s[20][20];
int cal(char *a,char *b){
int sum=0;
int lena=strlen(a),lenb=strlen(b);
for(int i=0;i<lena;++i){
int x=i,y=0,ans=0;
while(x<lena && y<lenb){
if(a[x] == b[y])++ans;
++x,++y;
}
sum=max(sum,ans);
}
for(int i=0;i<lenb;++i){
int x=i,y=0,ans=0;
while(x<lenb && y<lena){
if(b[x] == a[y])++ans;
++x,++y;
}
sum=max(sum,ans);
}
return sum;
}
void DP(){
int bit=1<<n;
memset(dp,-1,sizeof dp);
for(int i=0;i<n;++i)dp[1<<i][i]=0;
for(int i=1;i<bit;++i){
for(int j=0;j<n;++j){
if(dp[i][j] == -1)continue;
for(int k=0;k<n;++k){
if(i&(1<<k))continue;
dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+num[j][k]);
}
}
}
int sum=0;
for(int i=0;i<n;++i)sum=max(dp[bit-1][i],sum);
printf("%d\n",sum);
}
int main(){
while(~scanf("%d",&n),n){
for(int i=0;i<n;++i)scanf("%s",s[i]);
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j)num[i][j]=num[j][i]=cal(s[i],s[j]);
}
DP();
}
return 0;
}
原文：http://blog.csdn.net/xingyeyongheng/article/details/22824633
评论（0）