首页 > 搜索 > DFS搜索 > HDU 3722-Card Game-字符串-[解题报告]HOJ
2015
02-21

HDU 3722-Card Game-字符串-[解题报告]HOJ

Card Game

问题描述 :

Jimmy invents an interesting card game. There are N cards, each of which contains a string Si. Jimmy wants to stick them into several circles, and each card belongs to one circle exactly. When sticking two cards, Jimmy will get a score. The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card. For example, if Jimmy sticks the card S1 containing "abcd" in front of the card S2 containing "dcab", the score is 2. And if Jimmy sticks S2 in front of S1, the score is 0. The card can also stick to itself to form a self-circle, whose score is 0.

For example, there are 3 cards, whose strings are S1="ab", S2="bcc", S3="ccb". There are 6 possible sticking:
1.  S1->S2, S2->S3, S3->S1, the score is 1+3+0 = 4
2.  S1->S2, S2->S1, S3->S3, the score is 1+0+0 = 1
3.  S1->S3, S3->S1, S2->S2, the score is 0+0+0 = 0
4.  S1->S3, S3->S2, S2->S1, the score is 0+3+0 = 3
5.  S1->S1, S2->S2, S3->S3, the score is 0+0+0 = 0
6.  S1->S1, S2->S3, S3->S2, the score is 0+3+3 = 6
So the best score is 6.

Given the information of all the cards, please help Jimmy find the best possible score.

输入:

There are several test cases. The first line of each test case contains an integer N (1 <= N <= 200). Each of the next N lines contains a string Si. You can assume the strings contain alphabets (‘a’-'z’, ‘A’-'Z’) only, and the length of every string is no more than 1000.

输出:

There are several test cases. The first line of each test case contains an integer N (1 <= N <= 200). Each of the next N lines contains a string Si. You can assume the strings contain alphabets (‘a’-'z’, ‘A’-'Z’) only, and the length of every string is no more than 1000.

样例输入:

3
ab
bcc
ccb
1
abcd

样例输出:

6
0

把i 和 j写错了 找得人都要抓狂了。。

题意:

给出n个字符串,其中任意两个字符串(包括同一字符串)可以进行互相拼接起来,例如s1=”abcd”……>s2=”dcab”,表示将s1拼接在s2后面,所得的值就是将s1反转得”dcba”,该字符串与s2同有的前缀为”dc”,所以值就是2.现在求解在n个字符串给定的情况下,将这些字符串拼接起来所得到的最大值.
关键是建图,之后运用KM算法,ok!

 

 #include<iostream>
 #include<string.h>
 #include<stdio.h>
 int mark[1002],n;
 char ss[202][1020];
 int g[202][202],s[202],t[202],lx[202],ly[202],link[202],d[202];
 char temp[1002];
 
 int max(int x,int y)
 {
     return x<y?y:x;
 }
 
 int min(int x,int y)
 {
     return x<y?x:y;
 }
 
 void rev(int x,int len)
 {
     int i,j;
     for(i=0,j=len-1;i<len;i++,j--)
         temp[j]=ss[x][i];
 }
 
 void build()
 {
     int i,j,len,k,count;
     for(i=0;i<n;i++)
         for(j=0;j<n;j++)
         {
             if(i==j)
             {
                 g[i][j]=0;
                 continue ;
             }
             len=strlen(ss[i]);
             rev(i,len);
             count=0; int len2=strlen(ss[j]);
             for(k=0;temp[k]==ss[j][k]&&k<len&&k<len2;k++)
                 count++;
             g[i][j]=count;
         }
 }
 
 int dfs(int x)
 {
     s[x]=1;
     for(int i=0;i<n;i++)
     {
         
         if(t[i]==1)
             continue;int temp=lx[x]+ly[i]-g[x][i];
         if(temp==0)
         {
             t[i]=1;
             if(link[i]==-1||dfs(link[i]))
             {
                 link[i]=x;
                 return 1;
             }
         }
         else d[i]=temp<d[i]?temp:d[i];
     }
     return 0;
 }
 
 void update()
 {
     int i,j;
     int a=1<<30;
 //    for(i=0;i<n;i++)
     //    if(s[i])
             for(j=0;j<n;j++)
                 if(!t[j])
                     a=min(a,d[j]);
    for(i=0;i<n;i++)
    {
        if(s[i]) lx[i]-=a;
        if(t[i]) ly[i]+=a;
    }
 }
 
 
 
 void KM()
 {
     int i,j;
     for(i=0;i<n;i++)
     {
         lx[i]=ly[i]=g[i][0];
         for(j=0;j<n;j++)
             lx[i]=max(lx[i],g[i][j]);
     }
     memset(link,-1,sizeof(link));
     for(i=0;i<n;i++)
     {
         for(j=0;j<n;j++)
             d[j]=1<<30;
         while(1)
         {
             memset(s,0,sizeof(s));
             memset(t,0,sizeof(t));
             if(dfs(i))
                 break;
             else update();
         }
     }
 }
 
 
 int main()
 {
     int i,j;
     while(scanf("%d",&n)!=EOF)
     {
         for(i=0;i<n;i++)
             scanf("%s",ss[i]);
         build();
         KM();
         for(i=0;i<n;i++)
             dfs(i);
         int ans=0;
         for(i=0;i<n;i++)
             ans+=g[link[i]][i];
         
         printf("%d\n",ans);
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/assult/archive/2013/08/17/3264929.html


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。