首页 > 代码库 > bzoj4275 [ONTAK2015]Badania naukowe
bzoj4275 [ONTAK2015]Badania naukowe
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4275
【题解】
考虑预处理出来a[1..i]和b[1..j]的LCS,记为$f_{i,j}$;a[i..n]和b[j..m]的LCS,记为$g_{i,j}$。
同时预处理出来如果从a[i]开始匹配c串,终止位置,记为$af_i$;同理记录$bf_i$。
那么枚举c串在A,B中开始的位置$i$和$j$,就有贡献为$f_{i-1,j-1} + |c| + g_{af_i+1, bf_i+1}$
直接做即可,复杂度$O(nm)$。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 3e3 + 10; const int mod = 1e9+7; int n, m, K; int a[N], b[N], c[N]; int f[N][N], g[N][N], af[N], bf[N]; int main() { cin >> n; for (int i=1; i<=n; ++i) scanf("%d", a+i); cin >> m; for (int i=1; i<=m; ++i) scanf("%d", b+i); cin >> K; for (int i=1; i<=K; ++i) scanf("%d", c+i); for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) { f[i][j] = max(f[i-1][j], f[i][j-1]); if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1); } for (int i=n; i; --i) for (int j=m; j; --j) { g[i][j] = max(g[i+1][j], g[i][j+1]); if(a[i] == b[j]) g[i][j] = max(g[i][j], g[i+1][j+1] + 1); } if(!K) { cout << f[n][m] << endl; return 0; } for (int i=1; i<=n; ++i) { int k = 0; af[i] = n+1; for (int j=i; j<=n; ++j) { if(a[j] == c[k+1]) ++k; if(k == K) { af[i] = j; break; } } } for (int i=1; i<=m; ++i) { int k = 0; bf[i] = m+1; for (int j=i; j<=m; ++j) { if(b[j] == c[k+1]) ++k; if(k == K) { bf[i] = j; break; } } } // for (int i=1; i<=n; ++i) cout << af[i] << ‘ ‘; cout << endl; // for (int i=1; i<=m; ++i) cout << bf[i] << ‘ ‘; cout << endl; int ans = -1; for (int i=1, ii, jj; i<=n; ++i) for (int j=1; j<=m; ++j) { ii = af[i], jj = bf[j]; if(ii == n+1 || jj == m+1) continue; ans = max(ans, f[i-1][j-1] + g[ii+1][jj+1] + K); } cout << ans; return 0; }
bzoj4275 [ONTAK2015]Badania naukowe
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。