http://acm.pku.edu.cn/JudgeOnline/problem?id=1159
tle的代碼：
???#include?
<
iostream
>
#include?
<
stdio.h
>
using
?
namespace
?std;
short
?a[
5010
][
5010
]?
=
?
{
0
}
;
char
?p[
5010
];
int
?main()
{
????
int
?l;
????
int
?i,?j?,?t,?k?
=
?
1
;
????
while
(scanf(
"
%d%s
"
,
&
l,p)
!=
EOF)
????
{
????????k?
=
?
1
;
????????
//
下面for語句產生l=5000的測試數據；
?
/**/
/*
???????l?=?5000;
????????for(i?=?0;?i?<?5000;?i++)
????????????p[i]?=?'b';
????????p[0]?=?'1';
????????p[i]?=?'\0';
????????
*/
????????
for
(t?
=
?
1
;?t?
<
?l;?t
++
)
????????
{
???????????
for
(i?
=
?
0
;i
<
l
-
t;i
++
)
???????????
{
???????????????j?
=
?i?
+
?t;
???????????????
if
(p[i]?
==
?p[j])
{
????????????????????
//
k++;
???????????????????
//
把下面的換成k++對l=5000這組數據時間就不用那么多了，為什么啊？不都是一次運算么,運算時間不是相同的？
???????????????????a[i][j]?
=
?a[i
+
1
][j
-
1
];
???????????????}
???????????????
else
{
????????????????????
if
(a[i
+
1
][j]
<
a[i][j
-
1
])a[i][j]
=
a[i
+
1
][j]
+
1
;
????????????????????
else
?a[i][j]
=
a[i][j
-
1
]
+
1
;
???????????????}
???????????}
;
????????}
;
????????printf(
"
%d\n
"
,?a[
0
][l
-
1
]);
????}
????
return
?
0
;
}
ac的代碼：
#include?<stdio.h>
int?main()
{
????int?a[2][5002]={0};
????char?p[5002];
????char?ch[5002];
????int?i,j,n,t;
????int?current;
????int?before;
????scanf("%d%s",&n,p+1);
????????current=1;
????????before?=?0;
????????for(i=1;i<=n;i++)
???????????ch[i]=p[n-i+1];
???????????ch[i]='\0';
?????//???printf("%s?%s\n",p+1,ch+1);
????????for(i=1;i<=n;i++)
????????{????for(j=1;j<=n;j++)
????????????????if(ch[i]==p[j])
???????????????????a[current][j]=a[before][j-1]+1;
????????????????else
????????????????????if(a[current][j-1]>=a[before][j])a[current][j]=a[current][j-1];
????????????????????else?a[current][j]=a[before][j];
??????????????t=current;
??????????????current=before;
??????????????before=t;
????????}
????????printf("%d\n",n-a[t][n]);
????return?0;
}