Pat1040

题意是找最长对称子序列&＃xff0c;我的算法先将子序列翻转&＃xff0c;然后找最长公共连续子序列&＃xff0c;同样是用动态规划&＃xff0c;和LCS不同的是状态函数

#include
#includeusing std::cin;
using std::cout;
using std::endl;char str[1010],rstr[1010];
int m[1010][1010];
int max(int a, int b){return a > b ? a : b;
}
int LongestSym(char str[],char rstr[]){int length &＃61; strlen(str);int maxlen &＃61; 0, i, j, flag &＃61; 0,len &＃61; 0;for (i &＃61; 0; i 0][i] &＃61; 0;m[i][0] &＃61; 0;}for (i &＃61; 1; i <&＃61; length; i&＃43;&＃43;)for (j &＃61; 1; j <&＃61; length; j&＃43;&＃43;){if (str[i - 1] &＃61;&＃61; rstr[j - 1])m[i][j] &＃61; m[i - 1][j - 1] &＃43; 1;else m[i][j] &＃61; 0;if (m[i][j]>maxlen)maxlen &＃61; m[i][j];}return maxlen;
}
void reverse(char str[]){int len &＃61; strlen(str);int i, j;for (i &＃61; 0, j &＃61; len - 1; j >&＃61; 0; j--, i&＃43;&＃43;)rstr[i] &＃61; str[j];rstr[i] &＃61; &＃39;\0&＃39;;
}
int main(){freopen("1.in", "r", stdin);cin.get(str,1009);reverse(str);int longest &＃61; LongestSym(str,rstr);cout <return 0;
}