动态规划_基础_最长公共子序列_多种方法_递归/dp
2024-09-05 15:03:10
D: 魔法少女资格面试
题目描述
众所周知,魔法少女是一个低危高薪职业。随着近年来报考魔法少女的孩子们越来越多,魔法少女行业已经出现饱和现象!
为了缓和魔法少女界的就业压力,魔法少女考核员丁丁妹决定增加魔法少女资质考核的难度。
然而,即使如此,通过资质考核的魔法少女们数量仍然过多,因此,丁丁妹决心增加一轮面试,从而淘汰掉更多的预备魔法少女。
具体而言,她打算对所有面试者询问这样一个问题:
给两个长度为
n
的全排列,它们的最长公共子序列长度是多少?
不幸的是,由于丁丁妹没有好好上过学,她自己也不知道答案是多少,因此她使用魔法找到了你,希望你来帮她解决这个问题。
输入描述
每个测试点仅有一组数据。
第一行是一个正整数
n
,表示全排列长度。
第二行有
n
个整数,保证是一个
n
的全排列。
第三行有
n
个整数,保证是一个
n
的全排列。
其中,保证
1
≤
n
≤
1000
。
输出描述
输出一行一个整数,表示两数组的最长公共子序列长度。
样例输入
5
1 3 2 4 5
5 2 3 1 4
样例输出
2
Hint
如果你愿意思考
1
≤
n
≤
1000000
时的解法,那么丁丁妹会很高兴地录取你。
题解思路
这道题思路比较明显的,关系式就是:
也可以从后往前写成
L(i,j)=L(i+1,j+1)取等
L(i,j)=max(L(i,j+1),L(i+1,j))不等
但是这个式子我用递归直接写,就给TE了,如下为代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long ll;
const int M=1e3+;
int n;
int a[M],b[M];
int ans=; int dfs(int x,int y) {
int t=;
if(y>n||x>n) {
return t;
} else if(a[x]==b[y]) {
t=+dfs(x+,y+);
} else {
int t1=dfs(x,y+);
int t2=dfs(x+,y);
t=max(t1,t2);
} ans=max(ans,t);
return t; }
/*
6
5 3 1 4 2 6
1 5 3 2 4 6
*/
int main() {
scanf("%d",&n);
for(int i=; i<=n; i++)scanf("%d",&a[i]);
for(int i=; i<=n; i++)scanf("%d",&b[i]);
dfs(,);
printf("%d\n",ans);
return ; }
改了一下,写成动态规划,将原本dfs(i,j)改写成dp【i】【j】存起来
i ,j,表示当前序列 — a,b,分别在哪个位置,dp【i】【j】表示在这一状态下,a1-- ai 与 b1-- bj,存在最大公共子序列的长度
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long ll;
const int M=1e3+;
int n;
int a[M],b[M];
int ans=;
int dp[M][M];
/*
int dfs1(int x,int y) {
int t=0;
if(y>n||x>n) {
return t;
} else if(a[x]==b[y]) {
t=1+dfs(x+1,y+1);
} else {
int t1=dfs(x,y+1);
int t2=dfs(x+1,y);
t=max(t1,t2);
} ans=max(ans,t);
return t; } int dfs(int x,int y) {
int t=0;
if(y<1||x<1) {
return t;
} else if(a[x]==b[y]) {
t=1+dfs(x-1,y-1);
} else {
int t1=dfs(x,y-1);
int t2=dfs(x-1,y);
t=max(t1,t2);
} ans=max(ans,t);
return t; }*/
/*
6
5 3 1 4 2 6
1 5 3 2 4 6
*/
void f() {
int i,j;
memset(dp,,sizeof(dp)); for( i=; i<=n; i++) {
for( j=; j<=n; j++) {
if(a[i]==b[j]) {
dp[i][j]=dp[i-][j-]+;
} else {
dp[i][j]=max(dp[i-][j],dp[i][j-]);
}
}
}
printf("%d\n",dp[n][n]); } int main() {
scanf("%d",&n);
for(int i=; i<=n; i++)scanf("%d",&a[i]);
for(int i=; i<=n; i++)scanf("%d",&b[i]);
f();
// int n1=n;
//dfs(n1,n1);
//printf("%d\n",ans);
return ; }
(AC代码)
最新文章
- 从直播编程到直播教育:LiveEdu.tv开启多元化的在线学习直播时代
- webpack之傻瓜式教程
- Nmap扫描手册
- session与cookie的区别---
- maven错误:Project configuration is not up-to-date with pom.xml
- Unity3D DF根据名称获取多个子控件代码
- Lamp源码包安装实录
- Android砖机救活(索爱MT15i)
- 1N系列稳压二极管参数
- WCF大文件传输服务
- js生成随机数的方法实例总结
- scrapy_ItemLoader
- SVG初尝试(一)
- M2项目测试
- nodemcu使用心得1
- C#提取双引号中的字符串
- java项目中常见的异常及处理
- linux cpu过高原因及代码定位
- servlet实现文件上传,预览,下载和删除
- java8新特性——接口中的静态方法与默认方法