首页 > ACM题库 > HDU-杭电 > HDU 3489-Necklace[解题报告]HOJ
2014
04-04

HDU 3489-Necklace[解题报告]HOJ

Necklace

问题描述 :

Henryy gave the princess of the kingdom of Henryy a necklace, which is made by a series of diamonds which are the most valuable among the world.
The necklace can be regarded as a string of diamonds. (Notice that it’s not a loop of them!) In the kingdom, another kind of necklace is very popular, but it is much less precious. If this kind of necklace is a sub-string (not sub-sequence) of the princess’, maybe somebody will use the fake one to replace a part of it, and this is quite dangerous. Thus, Henryy want to remove some of the diamonds off from the necklace to make it safer. This number, of course, should be as small as possible.

输入:

The first line contains an integer T (1 ≤ T ≤ 10) which means T test cases follow:
In each test case:
The first line is a string indicating the princess’ necklace with its length no more than 10000 and made up by characters from ‘a’ to ‘z’.
The second line is the common necklace, with its length no more than 1000 and also made up by characters from ‘a’ to ‘z’.
The two necklaces cannot be reversed. (For example, a necklace “abc” cannot be regarded as “cba”.)
A blank line is followed after each test case.

输出:

The first line contains an integer T (1 ≤ T ≤ 10) which means T test cases follow:
In each test case:
The first line is a string indicating the princess’ necklace with its length no more than 10000 and made up by characters from ‘a’ to ‘z’.
The second line is the common necklace, with its length no more than 1000 and also made up by characters from ‘a’ to ‘z’.
The two necklaces cannot be reversed. (For example, a necklace “abc” cannot be regarded as “cba”.)
A blank line is followed after each test case.

样例输入:

1
ababaa
aba

样例输出:

1

# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;

int p[1002][26],pre[1002],n,m;
char a[10002],b[1002];
int f[10002][1002];

void relax(int &i,const int&j){if(i>j) i=j;}

int main()
{
 int Case; scanf("%d",&Case);
 while(Case--){
 scanf("%s",a+1); scanf("%s",b+1);
 n = strlen(a+1); m = strlen(b+1);
 for(int i=1; i<=n; i++)a[i]-='a',b[i]-='a';
 int k = 0; pre[1] = 0;
 for(int i=2; i<=m; i++) {
 while(k && b[k+1]!=b[i]) k = pre[k];
 if(b[k+1] == b[i]) k++; pre[i]=k;
 }

 memset(p,0,sizeof(p));
 for(int i=1; i<=m; i++) p[i-1][b[i]]=i;
 for(int i=1; i<=m; i++)
 for(int j=0; j<26; j++)
 if(!p[i][j]) p[i][j] = p[pre[i]][j];
 for(int j=0; j<26; j++) p[m][j] = m;

 memset(f,0x7f,sizeof(f)); f[0][0]=0;
 for(int i=0; i<n; i++)
 for(int j=0; j<m; j++)
 if( f[i][j]<0x7f7f7f7f )
 relax(f[i+1][j], f[i][j]+1),
 relax(f[i+1][p[j][a[i+1]]], f[i][j]);
 int ans = n+1;
 for(int i=0; i<m; i++) relax(ans, f[n][i]);
 printf("%d\n",ans);
 }
 return 0;
}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。