[ACM] POJ1159解题报告, LCS

130 Replies

引用大牛lnmm的思路

设ch[1]..ch[n]表示字符串1至n位，i为左游标，j为右游标 ，则i从n递减，j从i开始递增。
min[i][j]表示i和j之间至少需要插入多少个字符才能对称,初始置全0 ,我们最终需要得到的值是min[1][n]. 则
if(ch[i]==ch[j])                                    //如果两个游标所指字符相同，向中间缩小范围
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 +  （min[i+1][j]和min[i][j-1]中的较小值）;     //如果不同，典型的状态转换方程

画个图

[cpp]
i\j 1 2 3 4 5
1 0 * * * *
2 0 0 * * *
3 0 0 * *
4 0 0 *
5 0 0
[/cpp]

求右上的三角形即可, 三个方向, 左, 下, 左下, 和算法导论里353页的图思路差不多, 意思不一样而已.
一个自以为比较有意思的空间优化是, 把头顺时针转45度看那个三角形.. 不讲了麻烦, 上代码..

404K 344MS G++
[cpp]
#include <stdio.h>

int main()
{
int n;
char a[5010];
scanf("%d",&n);
while(getchar()!=’\n’);
scanf("%s",a);

int c[10010];
for(int i=2;i<=2*n;i++) {
c[i]=0;
}

for(int x=1;x<=n-1;x++)
for(int i=1;i<=n-x;i++) {
int j=i+x;
char ai=a[i-1],aj=a[j-1];
if(ai==aj)
continue;
c[i+j]=c[i+j-1]<c[i+j+1]?c[i+j-1]:c[i+j+1];
c[i+j]++;
}
printf("%d\n",c[1+n]);

return 0;
}[/cpp]

130 thoughts on “[ACM] POJ1159解题报告, LCS”

Leave a Reply

Your email address will not be published. Required fields are marked *