http://acm.pku.edu.cn/JudgeOnline/problem?id=1159
tle的代码:
#include
<
iostream
>
#include
<
stdio.h
>
using
namespace
std;
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
short
a[
5010
][
5010
]
=
{
0
}
;
char
p[
5010
];
int
main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
l;
int
i, j , t, k
=
1
;
while
(scanf(
"
%d%s
"
,
&
l,p)
!=
EOF)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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
++
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for
(i
=
0
;i
<
l
-
t;i
++
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
j
=
i
+
t;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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);
![](/Images/OutliningIndicators/InBlock.gif)
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++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ 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;
}
![](/Images/OutliningIndicators/None.gif)