- 1
- #include
- 2
- #include
- 3
- #include
- 4
- #include
- 5
- #include
- 6
- #include
- 7
- #include
- 8
- #include
- 9
- #include
- 10
- #include
- 11
- #include<
- set
- >
- 12 using namespace std;
- 13
- typedef
- long long ll;
- 14
- typedef pair<
- int
- ,
- int
- >
- pll;
- 15 const int
- INF =
- 0x3f3f3f3f;
- 16 const int
- maxn =
- 1000
- +
- 5;
- 17
- 18 char str1[maxn],str2[maxn];
- 19
- 20 struct node
- 21 {
- 22 int len;
- 23 string str;
- 24 }f[maxn][maxn];
- 25
- 26 int main()
- 27 {
- 28 //freopen("in.txt","r",stdin);
- 29 while
- (gets(str1+
- 1))
- 30 {
- 31 int
- len = strlen(str1+
- 1);
- 32 for
- (
- int
- i=len;i>=
- 1
- ;i--
- )
- 33
- str2[i]=str1[len-i+
- 1];
- 34
- 35 for
- (
- int
- i=
- 0
- ;i<=len;i++
- )
- 36 {
- 37
- f[
- 0
- ][i].len=
- 0;
- 38
- f[
- 0
- ][i].str=
- "";
- 39 }
- 40
- 41 for
- (
- int
- i=
- 1
- ;i<=len;i++
- )
- 42 {
- 43 for
- (
- int
- j=
- 1
- ;j<=len;j++
- )
- 44 {
- 45 if
- (str1[i]==
- str2[j])
- 46 {
- 47
- f[i][j].len=f[i-
- 1
- ][j-
- 1
- ].len+
- 1;
- 48
- f[i][j].str=f[i-
- 1
- ][j-
- 1
- ].str+
- str1[i];
- 49 }
- 50 else
- 51 {
- 52 if
- (f[i][j-
- 1
- ].len > f[i-
- 1][j].len)
- 53 {
- 54
- f[i][j].len=f[i][j-
- 1].len;
- 55
- f[i][j].str=f[i][j-
- 1].str;
- 56 }
- 57 else if
- (f[i][j-
- 1
- ].len < f[i-
- 1][j].len)
- 58 {
- 59
- f[i][j].len=f[i-
- 1][j].len;
- 60
- f[i][j].str=f[i-
- 1][j].str;
- 61 }
- 62 else
- 63 {
- 64
- f[i][j].len=f[i-
- 1][j].len;
- 65
- f[i][j].str=min(f[i-
- 1
- ][j].str,f[i][j-
- 1].str);
- 66 }
- 67 }
- 68 }
- 69 }
- 70
- 71 int
- maxlen=
- f[len][len].len;
- 72 string
- line=
- f[len][len].str;
- 73
- 74 if
- (maxlen&
- 1)
- 75 {
- 76 for
- (
- int
- i=
- 0
- ;i<=maxlen/
- 2
- ;i++
- )
- 77
- printf(
- "%c",line[i]);
- 78 for
- (
- int
- i=maxlen/
- 2
- -
- 1
- ;i>=
- 0
- ;i--
- )
- 79
- printf(
- "%c",line[i]);
- 80 }
- 81 else
- 82 {
- 83 for
- (
- int
- i=
- 0
- ;i
- 2
- ;i++
- )
- 84
- printf(
- "%c",line[i]);
- 85 for
- (
- int
- i=maxlen/
- 2
- -
- 1
- ;i>=
- 0
- ;i--
- )
- 86
- printf(
- "%c",line[i]);
- 87 }
- 88
- printf(
- "\n");
- 89 }
- 90 return 0;
- 91
- }
来源: http://www.bubuko.com/infodetail-2214963.html