NoLazyForMe 2021-05-21 07:48 采纳率: 0%
浏览 38
已采纳

算法题——辉夜大小姐以下代码的复杂度是多少

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(a-1); i>=(b); i--)
#define qrep(i, q) for(auto i : q)
#define sz(a) (int)a.size()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int maxn = 1005;
const int logn = (log(maxn)/log(2))+5;
const int inf = 0x3f3f3f3f;
const ld eps = 1e-9;
char a[maxn],b[maxn];
int dp[maxn][maxn];
int solve(int x = -1)
{
	//std::ios::sync_with_stdio(false);
    //std::cin.tie(0);
    if(x != -1){
    	char infile[10] = "0.in";
		char outfile[10] = "0.out";
		infile[0] = outfile[0] = '0'+x;
		freopen(infile, "r", stdin);
		freopen(outfile, "w", stdout);
	}
	scanf("%s%s", a+1, b+1);
	int n = strlen(a+1);
	int m = strlen(b+1);
	memset(dp, 0, sizeof dp);
	rep(i, 1, n+1){
		rep(j, 1, m+1){
			if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1;
			else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
		}
	}
	cout << dp[n][m] << endl;
	if(x != -1){
		fclose(stdin);
		fclose(stdout);
	}
	return 0;
}
int main(){
	//for(int i = 0;i < 10;i++) solve(i);
	solve();
}

 

 

展开全部

  • 写回答

2条回答 默认 最新

  • NoLazyForMe 2021-05-21 07:50
    关注

    O(N^2)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)
编辑
预览

报告相同问题?

悬赏问题

  • ¥15 KeiI中头文件找不到怎么解决
  • ¥15 QT6将音频采样数据转PCM
  • ¥15 本地安装org.Hs.eg.dby一直这样的图片报错如何解决?
  • ¥15 下面三个文件分别是OFDM波形的数据,我的思路公式和我写的成像算法代码,有没有人能帮我改一改,如何解决?
  • ¥15 Ubuntu打开gazebo模型调不出来,如何解决?
  • ¥100 有chang请一位会arm和dsp的朋友解读一个工程
  • ¥50 求代做一个阿里云百炼的小实验
  • ¥15 查询优化:A表100000行,B表2000 行,内存页大小只有20页,运行时3页,设计两个表等值连接的最简单的算法
  • ¥15 led数码显示控制(标签-流程图)
  • ¥20 为什么在复位后出现错误帧
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部