赤峰网站制作,c网站开发视频,单页营销网站后台,网站搭建工作题目#xff1a;http://poj.org/problem?id1159 思路: 找出原串的最长回文子串#xff0c;当然这里说的回文子串可以不连续。用原串的长度减去最长回文子串的长度即可得出结果。 设原串a[5001],它的反串为b[5001],求出a和b的最长公共子串的长度#xff08;可以不连续#… 题目http://poj.org/problem?id1159 思路: 找出原串的最长回文子串当然这里说的回文子串可以不连续。用原串的长度减去最长回文子串的长度即可得出结果。 设原串a[5001],它的反串为b[5001],求出a和b的最长公共子串的长度可以不连续即为回文子串的长度。再用原串长度减去回文子串的长度即可。 用动态规划求公共子串的长度m[5001][5001]打表。m[i][j]表示原串a第1个到第i个和反串b第1个到第j个的最长公共子串的长度。所以有两种情况 (1)当a[i] b[j]时m[i][j]m[i-1][j-1] 1; (2) a[i] ! b[j]时m[i][j]max(m[i-1][j],m[i][j-1])。 所以m[len][len]就是最长公共子串的长度。len为原串的长度 算法正确性证明 比如abcdb最长回文串是bcb或bdb长度是35-32所以只需插入2个即可。为什么呢 因为回文串有两种形式aba或者abba,我们暂且把后面那两个b看成是一个这个没关系的便于解释。那么一个字符串就分成了两类字符了一个是回文串一个是非回文串假设把回文串的中间那个字符记成b那么b左边的非回文串和b右边的非回文串就不可能有交集如果有那交集部分就会归并到回文串里所以只需要在左边对称位置插入b右边的非回文字符在右边插入b左边的非回文字符。所以要插入的字符个数就是非回文字符的个数非回文字符就是回文字符串对原字符串的补集故原串长度减去回文串长度即可得解。 代码 #include stdio.h
#include stdlib.h
#include string.h
#define N 5001char a[N],b[N];unsigned short m[N][N];int main()
{int len,i,j,t;while(scanf(%d,len) ! EOF ){scanf(%s,a); t len -1;for(i len-1; i 0 ; --i)b[t-i] a[i] ;for(i 1 ; i len ; i)for(j 0 ; j i ; j) m[i][j] m[j][i] 0;for(i 0 ; i len ; i)m[i][i] 0;for(i 1 ; i len ; i){for(j 1 ; j len ; j){if(a[i-1] b[j-1])m[i][j] m[i-1][j-1] 1;elsem[i][j] m[i-1][j] m[i][j-1] ? m[i-1][j]:m[i][j-1];}}printf(%d\n,len - m[len][len]);} // system(pause);return 0;
} 开始用 int m[N][N]; 超内存了用unsigned short 就AC了。 看discuss人家用滚动数组汗落伍了。第一次听说这玩意于是诚信学习了啊 先贴个最简单的滚动数组的应用求Fabonacci数列的第100个数 int d[3];d[0]1;d[1]1;for(i2;i100;i)d[i%3]d[(i-1)%3]d[(i-2)%3];printf(%d,d[99%3]);注意上面的运算我们只留了最近的3个解数组好象在“滚动‿一样所以叫滚动数组。 好了这个题就可以用滚动数组DP AC了。用一个二位的数组m[2][N]。列可以往后展开行不停的滚动 滚动方式 i%2,(i-1)%2 代码 #include stdio.h
#include stdlib.h
#include string.h
#define N 5001unsigned short m[2][N];
char a[N],b[N];int main()
{int len,i,j,t;while(scanf(%d,len) ! EOF ){scanf(%s,a); t len -1;for(i len-1; i 0 ; --i)b[t-i] a[i] ;for(i 0 ; i len ; i) m[0][i] m[1][i] 0;for(i 1 ; i len ; i){for(j 1 ; j len ; j){if(a[i-1] b[j-1])m[i%2][j] m[(i-1)%2][j-1] 1;elsem[i%2][j] m[(i-1)%2][j] m[i%2][j-1] ? m[(i-1)%2][j]:m[i%2][j-1];}}printf(%d\n,len - m[len%2][len]); } //system(pause);return 0;
} 转载于:https://www.cnblogs.com/HpuAcmer/archive/2012/05/03/2481323.html
