AGC026E Synchronized Subsequence <贪心+DP>

Problem

Synchronized Subsequence

$\mathrm{Time\;limit:\;2\;Sec}$
$\mathrm{Memory\;limit:\;1024\;MB}$

Statement

You are given a string $S$ of length $2N$, containing $N$ occurrences of a and $N$ occurrences of b.
You will choose some of the characters in $S$. Here, for each $i=1,2,\cdots,N$, it is not allowed to choose exactly one of the following two: the $i^{th}$ occurrence of a and the $i^{th}$ occurrence of b. (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order).
Find the lexicographically largest string that can be obtained in this way.

Constraints

$1\le N\le3000$
$S$ is a string of length $2N$ containing $N$ occurrences of a and $N$ occurrences of b.

Input

Input is given from Standard Input in the following format:
$N\\S$

Output

Print the lexicographically largest string that satisfies the condition.

Sample

Input #1

3
aababb

Output #1

abab

Explanation #1
A subsequence of $T$ obtained from taking the first, third, fourth and sixth characters in $S$, satisfies the condition.
Input #2

3
bbabaa

Output #2

bbabaa

Explanation #2
You can choose all the characters.
Input #3

6
bbbaabbabaaa

Output #3

bbbabaaa

Input #4

9
abbbaababaababbaba

Output #4

bbaababababa

标签：贪心 DP

Translation

给出一个长为$2N$的仅由a和b组成的字符串，每次可以删除第$i$个a和第$i$个b。求最终形成的字典序最大的串。

Solution

首先将整个串分为若干段，每一段都保证a的个数和b的个数相等。
设第$i$对a,b的位置分别为$p_i,q_i$，那么每一段中满足以下两种条件之一：

1. $\forall i,\;p_i<q_i$
2. $\forall i,\;p_i>q_i$

对于$情况1$，显然最后的串是abab...的形式，于是直接贪心从前往后选，对于当前这一对$(a,b)$如果a的位置在上一次选的$(a,b)$的b的位置之后，即可选当前这一对。
对于$情况2$，如果选了中间的某一组$(b,a)$，则其后面的$(b,a)$都选一定比不选要优。于是枚举哪一组$(b,a)$开始选，贪心求出字典序最大的串。
如此，可以将每一段都处理成能变成的字典序最大的串。最后需要考虑的就是拼起来。
显然，对于某一段，只有选和不选两种可能，于是用$f[i]$表示选第$i$段做开头，后面的串可以任意选，能得到的字典序最大的串（这里$f$是一个$string$数组）。那么$f[i]=\max_{j>i}\lbrace S[i]+f[j]\rbrace$。这样可以$O(n^2)$做$\mathrm{DP}$。最后的答案为$ans=\max_{i=1}^{m}\lbrace f[i]\rbrace$。

附上官方题解

Code

#include <bits/stdc++.h>
#define MAX_N 3000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
vector <string> S;
string s, f[MAX_N+5];
string sol() {
    vector <int> a, b, id, p;
    for (int i = 0; i < (int)s.size(); i++)
        if (s[i] == 'a') a.push_back(i);
        else b.push_back(i);
    for (int i = 0, pa = 0, pb = 0; i < (int)s.size(); i++)
        if (s[i] == 'a') id.push_back(pa), p.push_back(b[pa]), pa++;
        else id.push_back(pb), p.push_back(a[pb]), pb++;
    string ret = "";
    if (s[0] == 'a') {
        for (int i = 0; i < (int)s.size(); i++)
            if (s[i] == 'a') ret += "ab", i = p[i];
    } else {
        for (int i = (int)id.size()-1; ~i; i--) {
            string ss = "";
            for (int j = 0; j < (int)s.size(); j++)
                if (id[j] >= i) ss.push_back(s[j]);
            ret = max(ret, ss);
        }
    }
    return ret;
}
int main() {
    int n; read(n); string str; cin >> str, s = "";
    for (int i = 0, cnt = 0; i < (int)str.size(); i++) {
        s.push_back(str[i]), cnt += str[i] == 'a' ? 1 : -1;
        if (!cnt) S.push_back(sol()), s.clear();
    }
    string ans = "";
    for (int i = (int)S.size()-1; ~i; i--) {
        f[i] = S[i];
        for (int j = i+1; j < (int)S.size(); j++)
            f[i] = max(f[i], S[i]+f[j]);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}