九度OJ 1042：Coincidence（公共子序列） （DP）
2024-08-29 21:32:29
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：2303
解决：1241
- 题目描述：
-
Find a longest common subsequence of two strings.
- 输入：
-
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
- 输出：
-
For each case, output k – the length of a longest common subsequence in one line.
- 样例输入：
-
abcd
cxbydz
- 样例输出：
-
2
思路：
动态规划，分别设置两个指针，分别从头到尾搜索两个数组，最后得到的就是最大值。
动态规划的关键方程是：
if(a[i]
== b[j]) res[i+1][j+1]
= res[i][j]+1;else res[i+1][j+1]
= max(res[i+1][j], res[i][j+1]);代码：
#include <stdio.h>
#include <string.h> #define N 100
#define max(a, b) (((a)>(b)) ? (a) : (b)) int main(void)
{
int na, nb, i, j;
char a[N+1], b[N+1];
int res[N+1][N+1]; while (scanf("%s%s", a, b) != EOF)
{
na = strlen(a);
nb = strlen(b);
memset(res, 0, sizeof(res));
for (i=0; i<na; i++)
{
for (j=0; j<nb; j++)
{
if (a[i] == b[j])
res[i+1][j+1] = res[i][j]+1;
else
res[i+1][j+1] = max(res[i+1][j], res[i][j+1]);
}
}
/*
for (i=1; i<=na; i++)
{
for (j=1; j<=nb; j++)
{
printf("%d ", res[i][j]);
}
printf("\n");
}
*/
printf("%d\n", res[na][nb]);
} return 0;
}
/**************************************************************
Problem: 1042
User: liangrx06
Language: C
Result: Accepted
Time:0 ms
Memory:912 kb
****************************************************************/
最新文章
- C# 表复制和数据行的复制说明(Clone、ImportRow 、Copy )
- [转载]MySQL5.5 配置文件 my.ini 1067错误
- python suds 一坑
- PHP模拟登录并获取数据
- ORA-12631 / TNS-12631: Username retrieval failed
- 解决fontawesome-webfont 被拦截的问题
- 成为Java GC专家（4）—Apache的MaxClients参数详解及其在Tomcat执行FullGC时的影响
- Codevs 1697 ⑨要写信
- Bitmap 与Drawable相互转换
- WPF Customize TabControl
- shu_1186 字符排列问题
- data按钮
- linux shell编程指南第十八章------控制流结构
- centos下chm阅读器
- 【LeetCode每天一题】Swap Nodes in Pairs
- bind的封装
- ImportError: sys.meta_path is None, Python is likely shutting down
- JDBC方式执行SQL，支持CRUD返回LIST
- 怎样将Android SDK源码 导入到Eclipse中？
- 39 - 同步-异步-IO多路复用