Microsoft.Cpp.Chengdacaizi
天行健,君子以自强不息 地势坤,君子以厚德载物
北航 1066 最长公共子序列的长度
//================================================================================
//此题是求最长公共子学列,但是和一般题不同的是,内存卡的很严,是80kb,所以,要考虑状态的压缩,
//其实每次状态转移的时候都是用到了仅仅两个状态而已,故而用两个数组就可以保存所有有用的状态了
//开始想了好多的办法,后来算了算,那些优化简直可笑,不压缩是不可能过的。
//================================================================================
1
#include
<
iostream
>
2
#include
<
string
>
3
#define
MAXN 1005
4
using
namespace
std;
5
6
int
dp_1[MAXN];
7
int
dp_2[MAXN];
8
string
s_1;
9
string
s_2;
10
int
main()
11
{
12
freopen(
"
acm.acm
"
,
"
r
"
,stdin);
13
int
t;
14
int
i;
15
int
j;
16
cin
>>
t;
17
while
(t
--
)
18
{
19
cin
>>
s_1;
20
cin
>>
s_2;
21
for
(i
=
0
; i
<=
s_1.length();
++
i)
22
{
23
dp_1[i]
=
0
;
24
}
25
for
(j
=
0
;j
<=
s_2.length();
++
j)
26
{
27
dp_2[j]
=
0
;
28
}
29
for
(i
=
0
; i
<
s_1.length();
++
i)
30
{
31
for
(j
=
0
; j
<
s_2.length();
++
j)
32
{
33
if
(s_1[i]
==
s_2[j])
34
{
35
dp_1[j
+
1
]
=
dp_2[j]
+
1
;
36
}
37
else
38
{
39
if
(dp_2[j
+
1
]
>
dp_1[j])
40
{
41
dp_1[j
+
1
]
=
dp_2[j
+
1
];
42
}
43
else
44
{
45
dp_1[j
+
1
]
=
dp_1[j];
46
}
47
}
48
}
49
for
(j
=
0
; j
<=
s_2.length();
++
j)
50
{
51
dp_2[j]
=
dp_1[j];
52
}
53
}
54
//
cout<<dp_1[s_1.length()]<<endl;
55
cout
<<
dp_1[s_2.length()]
<<
endl;
56
57
}
58
}
59
60
61
62
posted on 2010-06-13 19:37
成大才子
阅读(252)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 成大才子
<
2010年8月
>
日
一
二
三
四
五
六
25
26
27
28
29
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
31
1
2
3
4
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 16
文章 - 1
评论 - 4
引用 - 0
公告
关于更多关于成大才子,请访问http://hi.baidu.com/成大才子
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔档案
2011年2月 (1)
2011年1月 (5)
2010年8月 (1)
2010年7月 (1)
2010年6月 (5)
2009年3月 (3)
文章分类
ACM(1)
(rss)
文章档案
2010年6月 (1)
链接
POJ
成大才子之百度空间
搜索
最新评论
1. re: poj 1101
@rayafjyblue
呵呵,好像不是那个原因。
--caizi
2. re: poj 1101
数组开78大概是因为字符串数组的每一行都有个‘\0’吧,所以要大一点。。。。。偶也是菜鸟。。。。
--rayafjyblue
3. re: 北航 1066 求最长公共子学列
很好的小题。
--成大才子
4. re: pku 3705
你就是传说中的成大才子??
久仰久仰
--NightMare
阅读排行榜
1. poj 1101(691)
2. linux 下获取系统函数的方法(660)
3. csharp静态构造器(650)
4. poj 3628(307)
5. 关于this索引器(288)
评论排行榜
1. poj 1101(2)
2. pku 3705(1)
3. 大早晨的~呵呵,附上1154(0)
4. poj 2726(0)
5. 北航 1066 最长公共子序列的长度(0)