首页 > ACM题库 > HDU-杭电 > HDU 4271-Find Black Hand-动态规划-[解题报告]HOJ
2015
05-23

HDU 4271-Find Black Hand-动态规划-[解题报告]HOJ

Find Black Hand

问题描述 :

I like playing game with my friends, although sometimes look pretty naive. Today I invent a new game called find black hand. The game is not about catching bad people but playing on a string.
Now I generate a string S and several short ones s[i], and I define three kinds of operations.
1. Delete: remove the ith character.
2. Insert: in any position, insert a character if you like.
3. Change: change the ith character into another character if you like.
For each short string s[i], we define a function f(i). After several operations on S, we can find a substring of S which is the same to s[i]. And f(i) is the minimal number of operations to achieve. It looks so native that I think every one of you can solve f(i) perfectly. So I join the string S from end to end, and f(i) changes nothing. So the string "bb" is also a substring of string "baaab".
The "black hand" is the short string s[i] whose f(i) is minimal. Now it’s your time to find the black hand.

输入:

There are multiple test cases.
The first line contains a non-empty string S whose length is not more than 100,000.
The next line contains an integer N (1 <= N <= 10) indicating the number of the short string.
Each of the next N lines contains a short non-empty string whose length is not more than 10.
All strings in the input would not have blank and all characters are lower case.

输出:

There are multiple test cases.
The first line contains a non-empty string S whose length is not more than 100,000.
The next line contains an integer N (1 <= N <= 10) indicating the number of the short string.
Each of the next N lines contains a short non-empty string whose length is not more than 10.
All strings in the input would not have blank and all characters are lower case.

样例输入:

aaabbbb
2
alice
bob

样例输出:

bob 1

本题目就是给定最多是个小串,和一母串,f(i)为将母串做至少f(i)次修改产生子串si,求min(f(i))

但是母串是可以首位相连的。

那么如果母串长l1 >= 小串长l2 , 那么只需在母串后将首部十个拷贝到尾部,然后正常找f(i), l1<l2 暴力美剧所有l1串的起始位置 ,把长度为n的环拆成 n个等价串再正常找。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define to first
#define val second
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,x,y) for(int i=x;i<=(int)y;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long long LL;
const int N = 1e5+100;
const int inf = 0x3f3f3f3f;

int d[12][N]={0};
int dp(char *s1,char *s2,int l1,int l2){
     int  tmp=inf;
     for(int i=1;i<=l1;i++){
         d[i][0]=i;
         for(int j=1;j<=l2;j++){
             d[i][j]=min(d[i-1][j-1]+(s1[i-1]!=s2[j-1]),min(d[i-1][j],d[i][j-1])+1);
             if(i==l1)  tmp=min(tmp,d[i][j]);
         }
     }
     return tmp;
 }
char src[15][15],str[N*2];
int main()
{
   while(scanf("%s",str)==1){
       int Q; scanf("%d",&Q);
       int ans = inf,po = 1;
       int l1 = strlen(str);
       for(int i=l1,j=0;j<15;i++,j++) str[i]=str[j];

       for(int i=1;i<=Q;i++){
           scanf("%s",src[i]);
           int l2 = strlen(src[i]);
           int te = inf;
           if(l1 < l2){
               for(int j=0;j<l1;j++){
                   te = min(te,dp(src[i],str+j,l2,l1));
               }
           }
           else {
                te = min(te, dp(src[i],str,l2,l1+min(20,l1)));
           }
           if(te < ans || (te==ans && strcmp(src[po],src[i])>0)){
                ans = te; po = i;
           }
       }
       printf("%s %d\n",src[po],ans);
   }
   return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/playwfun/article/details/48001405