POJ3267 The Cow Lexicon(dp)

题目链接

分析:

dp[i]表示母串从第i位起始的后缀所对应的最少去掉字母数。

dp[i] = min(dp[i+res]+res-strlen(pa[j]));

其中res 为从第 i 位开始匹配 pa[j] 所需要的长度。

以下代码当做指针的练习,研究了几天C,发现C语言功底到底是提升了(虽说算法功底至今还木有)。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> using namespace std; const int maxn = ; char s[maxn], pa[][];
int dp[maxn]; int match(char *s1, char *s2) {
char *p1 = s1, *p2 = s2; while(*p1 && *p2) {
if((*p1++ == *p2)) p2++;
} if(*p2) return ;
else return p1-s1;
} int main() {
int W, L, i, res; char (*p)[]; scanf("%d%d", &W, &L); scanf("%s", s); for(i=, p=pa; i<W; i++) {
scanf("%s", *p++);
} dp[L] = ;
for(int i=L-; i>=; i--) {
dp[i] = dp[i+]+;
for(int j=; j<W; j++)
if((res = match(&s[i], pa[j])))
dp[i] = min(dp[i], dp[i+res]+res-(int)strlen(pa[j]));
} printf("%d\n", dp[]); return ;
}
上一篇:【HDU 5572 An Easy Physics Problem】计算几何基础


下一篇:匿名类型和Object转换