首页 > ACM题库 > HDU-杭电 > HDU 3913-SUFFIX[解题报告]HOJ
2015
04-14

HDU 3913-SUFFIX[解题报告]HOJ

SUFFIX

问题描述 :

A string is a list of characters containing only letter ‘a’ to ‘z’. For example: “abcdefg”, “isun” are valid strings. “rocket323” is not a valid string.

A suffix of a string suf[i] is the list of characters at positions from i to n-1 (positions are labeled from 0 to n �C 1, n is length of the string). For the string “hustacm”, suf[0] = “hustacm”, suf[1] = “ustacm”, suf[3] = “tacm”, suf[6] = “m”.

The suffix list L of a string is a permutation of numbers from 0 to n-1(n is length of the string), which satisfy the following condition:
suf[L[0]] < suf[L[1]] < suf[L[2]] < … < suf[L[n-1]].

For the string “aabac”, its suffix list is [0, 1, 3, 2, 4].
Here comes the question: Given a string S and a suffix list L, you are to change minimum number of characters of S so that the suffix list of the new string is equal to L.

输入:

There are multiple cases, for each case:
  The first line is integer n representing the length of the string. (1 <= n <= 500)
  The second line is the string.
  The third line is a permutation of numbers from 0 to n-1.

输出:

There are multiple cases, for each case:
  The first line is integer n representing the length of the string. (1 <= n <= 500)
  The second line is the string.
  The third line is a permutation of numbers from 0 to n-1.

样例输入:

3
abc
0 1 2
3
aab
2 0 1

样例输出:

0
2

#include <cstdio>
#include <cstring>
const int inf = 0x3f3f3f3f;
int len, timeStamp;
char str[555];
int rank[555], sa[555];
int f[555][26];

	void upd(int &x, int y) {
		if ( y < x )
			x = y;
	}

int main() {
	while ( scanf("%d", &len) != EOF ) {
		scanf("%s", str);
		for ( int i = 0; i < len; i ++ ) 
			scanf("%d", &sa[i]);
		for ( int i = 0; i < len; i ++ ) 
			rank[sa[i]] = i;
		rank[len] = -1;
		memset(f, 0x3f, sizeof(f));
		for ( int a = 0; a < 26; a ++ )
			f[0][a] = a != (str[sa[0]] - 'a'); 
		for ( int i = 0; i < len - 1; i ++ ) {
			int p = sa[i], q = sa[i + 1];
			for ( int j = 0; j < 26; j ++ ) {
				for ( int k = j + 1; k < 26; k ++ )
					upd(f[i + 1][k], f[i][j] + (k != str[q] - 'a'));
				if ( rank[p + 1] < rank[q + 1] )
					upd(f[i + 1][j], f[i][j] + (j != str[q] - 'a'));
			}
		}
		int res = inf;
		for ( int a = 0; a < 26; a ++ )
			upd(res, f[len - 1][a]);
		if ( res == inf )
			printf("-1\n");
		else
			printf("%d\n", res);
	}
}