Luogu2543[AHOI2004]奇怪的字符串 (动态规划 LCS)
2024-09-02 10:30:15
04年的省选这么water吗,开个滚动数组算了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++ a)
#define nR(a,b,c) for(register int a = (b); a >= (c); -- a)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) a^=b^=a^=b
#define ll long long
#define ON_DEBUG
#ifdef ON_DEBUG
#define D_e_Line printf("\n\n----------\n\n")
#define D_e(x) cout << #x << " = " << x << endl
#define Pause() system("pause")
#else
#define D_e_Line ;
#endif
struct ios{
template<typename ATP>ios& operator >> (ATP &x){
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x*= f;
return *this;
}
}io;
using namespace std;
const int N = 10007;
char a[N], b[N];
int f[2][N];
int main(){
scanf("%s%s", a, b);
int lenA = strlen(a), lenB = strlen(b);
R(i,1,lenA)
R(j,1,lenB){
if(a[i-1] == b[j-1])
f[i&1][j] = f[(i-1)&1][j-1] + 1;
else
f[i&1][j] = Max(f[(i-1)&1][j], f[i&1][j-1]);
}
printf("%d", f[lenA&1][lenB]);
return 0;
}
最新文章
- ABP源码分析三十九:ABP.Hangfire
- Mysql字符串字段判断是否包含某个字符串的3种方法
- [大坑]FFT学习
- DSP using MATLAB 示例Example3.9
- notepad++查看aspx
- 在JavaScript中判断整型的N种方法
- 简易nagios安装出现的问题及解决方法
- Orchard源码分析(1):插件式的支持——模块和主题
- oracle查找重复记录
- 时间运算函数 CATT_ADD_TO_TIME
- java并发包下的并发工具类
- 模板语言变量,js变量,js自执行函数之前嵌套调用
- 学习go语言编程系列之helloworld
- inline元素、block元素、inline-block元素
- select 下拉选中
- python 读取bin文件
- centos6.3_gcc安装软件及流程
- Web API的发布问题
- Linux的vim和vi编辑器
- Redis数据持久化机制AOF原理分析一---转