注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

哈密顿回路与DP  

2009-07-08 17:43:22|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

WordStack
Accepted : 29    Submit : 61 
Time Limit : 1000 MS   Memory Limit : 65536 KB

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.
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 .
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
Source
Mid-Atlantic 2005
Hint
Note: One possible arrangement yielding this score is:
aaa

abc

 bcd

  cde

bfcde

题目大意:每两个单词之间有一个分数,这个分数是通过在单词前面增加空格得到的这两个单词之间对应位置相同的字符数。现在给定一组单词序列,要求找出一种排列方式,把每两个相邻的单词之间分数相加,使得总和最大。比如hint的排列方式,则有最大的分数为1+2+2+3=8;

主要思想:

1.如果把每个单词看成是一个点,那么分数就是每两个点之间边的权值。从上往下观察单词序列,就类似于遍历了一个图中的每一个顶点一次。所以这道题目就转化到求解一条权值之和最大的哈密顿回路(哈密顿回路是指从图中的一个顶点出发,经过每个顶点一次后回到出发点的一条路径)。

2.假设终点为e,且访问过的顶点集合为s(T),则对于哈密顿回路有状态转移方程f(e,s(T))=max{f(e*,s(T-1))+weight(e*,e)},其中f(e,s(T))表示当前访问过的顶点集合为s(T),最后一个访问的节点是e的最大权值。s(T-1)是指还没访问到e时所经过的顶点集合,当从状态s(T-1)要访问顶点e时,可以经过s(T-1)的其中一个顶点来访问。

3.每个顶点有访问和未访问两种状态,所以最多有2^10种状态,如果对这么多种状态来开数组来记录,则空间上是很浪费的,所以可以采用状态压缩,用一位二进制位表示对应位置上的顶点是否被访问过。

代码如下:

#include<iostream>
#define MAX 20
using namespace std;
struct EndState{
    int end:5;
    int state:11;
};   //前5为表示顶点的序号,后11位表示对应位置的访问状态
char word[MAX][MAX];
int w[MAX][MAX];     //记录每两个单词之间的权值
int dp[1100][MAX];    //用来记忆搜索
void Cal(int n);         //通过给定的单词计算w二维数组的值
int MaxScore(EndState es,int n);
int main(){
    int n;
    int i,j;
    int temp,max;
    EndState es;
    while(scanf("%d",&n),n>0){
        for(i=0;i<n;i++)scanf("%s",word[i]);
        Cal(n);

        es.state=(1<<n)-1;
        max=0;
        for(i=0;i<es.state+1;i++)
            for(j=0;j<n;j++)dp[i][j]=0;
        for(i=0;i<n;i++){  //分别计算终点为i的最大哈密顿回路
            es.end=i;
            temp=MaxScore(es,n);
            max=max<temp?temp:max;
        }
        printf("%d\n",max);
    }
    return 0;
}
void Cal(int n){
    int i,j,k,r;
    int max,temp;
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++){
             max=0;
             for(k=0;word[i][k];k=k-r+1){    //在word[j]上添加空格来计算分数
                 temp=0;
                 for(r=0;word[j][r]&&word[i][k];r++,k++)
                     if(word[j][r]==word[i][k])temp++;
                 max=max<temp?temp:max;
             }
             for(k=0;word[j][k];k=k-r+1){    //在word[i]上添加空格来计算分数
                 temp=0;
                 for(r=0;word[i][r]&&word[j][k];r++,k++)
                     if(word[i][r]==word[j][k])temp++;
                 max=max<temp?temp:max;
             }
             w[i][j]=w[j][i]=max;
        }
}
int MaxScore(EndState es,int n){
    int i;
    EndState est;
    int temp,max;
    est.state=es.state&(~(1<<es.end));    //前一种访问节点的状态是还没访问es.end时的状态
    if(est.state==0)return 0;       //如果前一种状态的值为0,说明已经回到了起点,直接返回0
    if(dp[es.state][es.end])return dp[es.state][es.end];   //如果已经计算计算过直接返回结果
    max=0;
    for(i=0;i<n;i++){
        temp=0;
        if((est.state&(~(1<<i)))!=est.state){     //只有之前访问过的节点才能再访问到es.end
            est.end=i;
            temp=MaxScore(est,n)+w[est.end][es.end];   //状态方程
            max=max<temp?temp:max;
        }
    }
    dp[es.state][es.end]=max;    //记录结果
    return max;
}

后记:

1.dp的关键点就是状态转移方程,而这也是我最头疼的地方,分析问题的能力有待提高。

2.在这道题目里也找到计算最长哈密顿回路的方法,状态压缩的思想值得借鉴。

3.state至少要是11位,而不能是10位,因为在计算机中会把state当成是有符号数来处理,所以当只取10位且最高位为1的时候,state在计算机中实际上就是一个负数了,在执行dp[es.state][es.end]的时候就会因为第一个下标为负数而RE了。

  评论这张
 
阅读(1117)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017