博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LCS(打印全路径) POJ 2264 Advanced Fruits
阅读量:7123 次
发布时间:2019-06-28

本文共 1535 字,大约阅读时间需要 5 分钟。

 

题意:两个字符串结合起来,公共的字符只输出一次

分析:LCS,记录每个字符的路径

 

代码:

/*    LCS(记录路径)模板题:            用递归打印路径:)*/#include 
#include
#include
#include
#include
using namespace std;const int N = 1e2 + 10;const int INF = 0x3f3f3f3f;char s[N], t[N];int dp[N][N];int fa[N][N];void print(int x, int y)  { if (!x && !y) return ; if (fa[x][y] == 0) { print (x-1, y-1); printf ("%c", s[x-1]); } else if (fa[x][y] == -1) { print (x-1, y); printf ("%c", s[x-1]); } else { print (x, y-1); printf ("%c", t[y-1]); }}void LCS(void) { int lens = strlen (s), lent = strlen (t); memset (dp, 0, sizeof (dp)); memset (fa, 0, sizeof (fa)); for (int i=0; i<=lens; ++i) fa[i][0] = -1; for (int i=0; i<=lent; ++i) fa[0][i] = 1; for (int i=1; i<=lens; ++i) { for (int j=1; j<=lent; ++j) { if (s[i-1] == t[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; fa[i][j] = 0; } else if (dp[i-1][j] >= dp[i][j-1]) { dp[i][j] = dp[i-1][j]; fa[i][j] = -1; } else { dp[i][j] = dp[i][j-1]; fa[i][j] = 1; } } } // printf ("%d\n", dp[lens][lent]); print (lens, lent); puts ("");}int main(void) { while (scanf ("%s %s", &s, &t) == 2) { LCS (); } return 0;}

  

转载于:https://www.cnblogs.com/Running-Time/p/4466906.html

你可能感兴趣的文章
统计嵌套数组中给定值的重要性 Employee Importance
查看>>
Redis Desktop Manager for mac
查看>>
redis_简单秒杀
查看>>
Oracle优化查询改写(第三章-操作多个表)
查看>>
注解、类加载器、代理
查看>>
GET和POST区别详解
查看>>
java.nio.ByteBuffer中flip、rewind、clear方法的区别
查看>>
秋色园QBlog技术原理解析:性能优化篇:数据库文章表分表及分库减压方案(十五)...
查看>>
PHP LFI to arbitratry code
查看>>
解决tomcat启动超时
查看>>
错误Name node is in safe mode的解决方法
查看>>
小黑小波比.Ubuntu下安装Intellij IDEA和java的环境变量
查看>>
程序员必备:项目时间估算技能
查看>>
Shell编程,read的用法
查看>>
gulp koa nodejs 实现的前段工程分离开发
查看>>
MySQL/HandlerSocket和VoltDB:NoSQL的竞争者
查看>>
Inside AbstractQueuedSynchronizer (2)
查看>>
VC组件之间的通信所需的端口
查看>>
POI操作Excel导入导出
查看>>
MFC edit control 用法
查看>>