#include <cstdio> #include <algorithm> using namespace std; using ll = long long int; using pll = pair<ll, ll>; using tll = pair<pll, pll>; #define e1 first.first #define e2 first.second #define e3 second.first #define e4 second.second const int MAXN = 4210;//100010; vector<tll> space[MAXN][MAXN]; ll A[MAXN]; ll B[MAXN]; vector<tll> extend(const vector<tll> &vec, ll val, bool source) { vector<tll> out(vec); for (int i = 0; i < vec.size(); i++) { out[i].e2 = max(0LL, out[i].e2 + val); out[i].e1 = max(out[i].e1, out[i].e2); out[i].e3 = source; out[i].e4 = i; } sort(out.begin(), out.end()); return out; } vector<tll> merge(const vector<tll> &a, const vector<tll> &b) { vector<tll> out; int i = 0; int j = 0; while (i < a.size() || j < b.size()) { tll next_pt; if (i == a.size()) { next_pt = b[j]; j++; } else if (j == b.size()) { next_pt = a[i]; i++; } else if (a[i] < b[j]) { next_pt = a[i]; i++; } else if (a[i] > b[j]) { next_pt = b[j]; j++; } else { next_pt = a[i]; i++; j++; } if (out.size() == 0 || (out.back().e1 < next_pt.e1 && out.back().e2 > next_pt.e2)) { out.push_back(next_pt); } } return out; } int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%lld", A + i); } for (int i = 1; i <= n; i++) { scanf("%lld", B + i); } space[0][0].push_back({{ 0, 0 }, { 0, 0 }}); for (int j = 0; j <= k; j++) { for (int i = 1; i <= n; i++) { vector<tll> xB = extend(space[i - 1][j], B[i], 0); if (j > 0) { vector<tll> xA = extend(space[i - 1][j - 1], A[i], 1); space[i][j] = merge(xB, xA); } else { space[i][j] = xB; } } } printf("%lld\n", space[n][k][0].e1); vector<char> picks; int id = 0; int kk = k; for (int nn = n; nn >= 1; nn--) { int nextid = space[nn][kk][id].e4; if (space[nn][kk][id].e3 == 1) { kk--; picks.push_back('A'); } else { picks.push_back('B'); } id = nextid; } for (int i = n - 1; i >= 0; i--) printf("%c", picks[i]); puts(""); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include <cstdio> #include <algorithm> using namespace std; using ll = long long int; using pll = pair<ll, ll>; using tll = pair<pll, pll>; #define e1 first.first #define e2 first.second #define e3 second.first #define e4 second.second const int MAXN = 4210;//100010; vector<tll> space[MAXN][MAXN]; ll A[MAXN]; ll B[MAXN]; vector<tll> extend(const vector<tll> &vec, ll val, bool source) { vector<tll> out(vec); for (int i = 0; i < vec.size(); i++) { out[i].e2 = max(0LL, out[i].e2 + val); out[i].e1 = max(out[i].e1, out[i].e2); out[i].e3 = source; out[i].e4 = i; } sort(out.begin(), out.end()); return out; } vector<tll> merge(const vector<tll> &a, const vector<tll> &b) { vector<tll> out; int i = 0; int j = 0; while (i < a.size() || j < b.size()) { tll next_pt; if (i == a.size()) { next_pt = b[j]; j++; } else if (j == b.size()) { next_pt = a[i]; i++; } else if (a[i] < b[j]) { next_pt = a[i]; i++; } else if (a[i] > b[j]) { next_pt = b[j]; j++; } else { next_pt = a[i]; i++; j++; } if (out.size() == 0 || (out.back().e1 < next_pt.e1 && out.back().e2 > next_pt.e2)) { out.push_back(next_pt); } } return out; } int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%lld", A + i); } for (int i = 1; i <= n; i++) { scanf("%lld", B + i); } space[0][0].push_back({{ 0, 0 }, { 0, 0 }}); for (int j = 0; j <= k; j++) { for (int i = 1; i <= n; i++) { vector<tll> xB = extend(space[i - 1][j], B[i], 0); if (j > 0) { vector<tll> xA = extend(space[i - 1][j - 1], A[i], 1); space[i][j] = merge(xB, xA); } else { space[i][j] = xB; } } } printf("%lld\n", space[n][k][0].e1); vector<char> picks; int id = 0; int kk = k; for (int nn = n; nn >= 1; nn--) { int nextid = space[nn][kk][id].e4; if (space[nn][kk][id].e3 == 1) { kk--; picks.push_back('A'); } else { picks.push_back('B'); } id = nextid; } for (int i = n - 1; i >= 0; i--) printf("%c", picks[i]); puts(""); } |