Standing on Shoulders of Giants
God Show me the way
C++博客
首页
新随笔
联系
聚合
管理
随笔 - 32 文章 - 2 trackbacks - 0
<
2008年4月
>
日
一
二
三
四
五
六
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(3)
给我留言
查看公开留言
查看私人留言
随笔档案
2008年11月 (26)
2008年6月 (1)
2008年4月 (5)
文章档案
2008年4月 (1)
搜索
积分与排名
积分 - 8798
排名 - 1247
最新评论
1. re: URAL 1024 Permutations
@zjhuijsj@163.com
讨论里面有
--Joseph
2. re: URAL 1024 Permutations
测试数据是怎么得到得
--zjhuijsj@163.com
阅读排行榜
1. pku题目分类(1097)
2. URAL 1090. In the army now(925)
3. URAL 1036 Lucky tickets(426)
4. 关于floyd求多源最短路循环顺序(394)
5. URAL 1095. Nikifor 3(346)
评论排行榜
1. URAL 1024 Permutations(2)
2. URAL 1029 Ministry(0)
3. URAL 1030 Titanic(0)
4. URAL 1031 Railway tickets(0)
5. URAL 1036 Lucky tickets(0)
pku 1159
比较基础的DP,统计字符串正序与逆序的最长公共子序列长度就可以了。
最开始是用Pascal写的,总超时。换C++,根本不需要优化。
1
#include
<
iostream
>
2
int
n;
3
char
list[
5001
]
=
{
0
}
;
4
short
int
dp[
5001
][
5001
]
=
{
0
}
;
5
int
max(
int
a,
int
b,
int
c)
{
6
if
(b
>
a) a
=
b;
7
if
(a
>
c)
return
a;
else
return
c;
8
}
9
int
main()
{
10
int
i,j,k
=
0
;
11
scanf(
"
%d\n
"
,
&
n);
12
for
(i
=
0
;i
<
n;i
++
) list[i]
=
getchar();
13
i
=
1
;
14
for
(i
=
1
;i
<=
n;i
++
)
{
15
for
(j
=
1
;j
<=
n;j
++
)
{
16
if
(list[i
-
1
]
==
list[n
-
j]) k
=
1
;
else
k
=
0
;
17
dp[i][j]
=
max(dp[i
-
1
][j],dp[i][j
-
1
],dp[i
-
1
][j
-
1
]
+
k);
18
}
19
}
20
printf(
"
%d\n
"
,n
-
dp[n][n]);
21
}
posted on 2008-04-11 21:30
Joseph
阅读(212)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理