NoLazyForMe
NoLazyForMe
2021-05-21 15:48
采纳率: 100%
浏览 25

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

#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
    NoLazyForMe 2021-05-21 15:50
    已采纳

    O(N^2)

    点赞 评论
  • NoLazyForMe
    NoLazyForMe 2021-05-21 16:01

    456789

    点赞 评论

相关推荐