hdu 3913 SUFFIX

本文从WordPress迁移而来, 查看全部WordPress迁移文章

【重做DP系列】

题意:给出一个只由小写字母组成的串,下面给出一个排序,a1,a2,a3……..an表示后缀串,问至少要改变多少个字母才能使原串的后缀串满足这个条件。

  1. 两个串比较大小,只由两种情况,s1[0] < s2[0],那么s1串小。s1[0] = s1[0],那么从下一位开始比较整个串即可
  2. 对于已经给出的排列,a1,a2,a3…….an,在处理完后,一定满足s[a1] <= s[a2] <= s[a3] <= s[a4] …….. <= s[an]
    如果是小于了,那么就成立,如果是等于还要进一步考虑ai的下一个字符是s[ai + 1],aj的下一个字符是s[aj + 1]如果r[ai + 1] < r[aj + 1]即,在列表中的排位前者者更小一点,就可以更新

整个dp是以列表给出的顺序dp下去的,而不是以串的顺序dp下去,对于但是位置,枚举当前字母可能的情况,即26个字母都枚举一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
不要以串的位置来dp,要以给出的list的序列来dp
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 510
#define INF 0x3f3f3f3f
#define cl memset
int n,dp[N][30],a[N],r[N];
char str[N];

int main(){
while(scanf("%d",&n)!=EOF){
scanf("%s",str);
for(int i = 0; i < n; i++){
scanf("%d",&a[i]);
r[a[i]] = i;
}
r[n] = -1;
cl(dp,0x3f,sizeof(dp));
for(int k = 0; k < 26; k++)
dp[0][k] = (str[a[0]] == 'a'+k ? 0 : 1);
for(int i = 1; i < n; i++)
for(int k = 0; k < 26; k++){
for(int c = 0; c < k; c++)
dp[i][k] = min(dp[i][k] , dp[i-1][c]);
if(r[a[i-1]+1] < r[a[i]+1])
dp[i][k] = min(dp[i][k] , dp[i-1][k]);
if(str[a[i]] != 'a'+k) dp[i][k]++;
}
int ans = INF;
for(int k = 0; k < 26; k++)
ans = min(ans,dp[n-1][k]);
printf("%d\n",ans == INF ? -1 : ans);
}
return 0;
}