首页 > ACM题库 > HDU-杭电 > HDU 2895-Edit distance -贪心-[解题报告]HOJ
2014
02-17

HDU 2895-Edit distance -贪心-[解题报告]HOJ

Edit distance

问题描述 :

Given a string, an edit script is a set of instructions to turn it into another string. There are
four kinds of instructions in an edit script:
Add (‘a’): Output one character. This instruction does not consume any characters
from the source string.
Delete (‘d’): Delete one character. That is, consume one character from the source string and output nothing.
Modify (‘m’): Modify one character. That is, consume one character from the source string and output a character.
Copy (‘c’): Copy one character. That is, consume one character from the source string and output the same character.
Now, We define that A shortest edit script is an edit script that minimizes the total number of adds and deletes.
Given two strings, generate a shortest edit script that changes the first into the second.

输入:

The input consists of two strings on separate lines. The strings contain only alphanumeric
characters. Each string has length between 1 and 10000, inclusive.

输出:

The input consists of two strings on separate lines. The strings contain only alphanumeric
characters. Each string has length between 1 and 10000, inclusive.

样例输入:

abcde
xabzdey

样例输出:

a x
a a
m b
m z
m d
m e
m y

题目链接

头一次做贪心这么给力。。。1Y,题意就是给俩字符串,如何把前一个变成后一个,4种操作,输出最短,且按 a d m c的优先级输出,分情况讨论下OK了。

PS:本来以为是二维DP,一看1W,我慌乱了。。。

#include <stdio.h>
 #include <string.h>
 char p1[10001],p2[10001];
 int main()
 {
     int i,j,len1,len2;
     while(scanf("%s%s",p1,p2)!=EOF)
     {
         len1 = strlen(p1);
         len2 = strlen(p2);
         if(len1 > len2)
         {
             for(i = 0;i <= len1-len2-1;i ++)
             printf("d %c\n",p1[i]);
             for(j = 0;j <= len2-1;j ++)
             {
                 printf("m %c\n",p2[j]);
             }
         }
         else if(len1 == len2)
         {
             for(i = 0;i <= len2-1;i ++)
             {
                 printf("m %c\n",p2[i]);
             }
         }
         else if(len1 < len2)
         {
             for(i = 0;i <= len2-len1-1;i ++)
             printf("a %c\n",p2[i]);
             for(j = len2-len1;j <= len2-1;j ++)
             printf("m %c\n",p2[j]);
         }
     }
     return 0;
 }

解题参考:http://www.cnblogs.com/naix-x/archive/2012/06/23/2559374.html


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。