Pagini recente » Cod sursa (job #2500985) | Cod sursa (job #1411525) | Cod sursa (job #1122390) | Cod sursa (job #2377261) | Cod sursa (job #2892936)
#include <bits/stdc++.h>
using namespace std;
int **d;
void read_input(vector<int> &a, vector<int> &b, string filename_in) {
ifstream in(filename_in);
size_t len;
in >> len;
a.resize(len);
in >> len;
b.resize(len);
for(size_t i = 0; i < a.size(); i++)
in >> a[i];
for(size_t i = 0; i < b.size(); i++)
in >> b[i];
in.close();
}
vector<int> solve_dp(vector<int> &a, vector<int> &b) {
vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
// Compute DP Array
for(size_t i = 0; i < a.size(); i++)
for(size_t j = 0; j < b.size(); j++) {
if(a[i] == b[j])
dp[i + 1][j + 1] = dp[i][j] + 1;
else
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
}
// Get length of maximum subset
int max_len = dp.back().back();
vector<int> res(max_len);
size_t res_pos = res.size();
// Get subset
int i = a.size() - 1;
int j = b.size() - 1;
while(i >= 0 && j >= 0) {
if(a[i] == b[j]) {
res[--res_pos] = a[i];
i--;
j--;
} else if(dp[i + 1][j] > dp[i][j + 1]) {
j--;
} else {
i--;
}
}
return res;
}
void write_output(vector<int> &res, string filename_out) {
ofstream out(filename_out);
out << res.size() << '\n';
for(int x : res)
out << x << ' ';
out.close();
}
int main() {
vector<int> a, b;
read_input(a, b, "cmlsc.in");
vector<int> res = solve_dp(a, b);
write_output(res, "cmlsc.out");
return 0;
}