Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- using namespace std;
- const int N = 17;
- string s[N];
- int dp[N][1 << N], maxDP[N][1 << N];
- vector <pair <string, int> > substrings[N];
- int main () {
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> s[i];
- for (int msk = 1; msk < (1 << s[i].length()); msk++) {
- string tmp = "";
- for (int j = 0; j < (int) s[i].length(); j++)
- if (msk & (1 << j))
- tmp += s[i][j];
- substrings[i].push_back ({tmp, msk});
- }
- sort (substrings[i].begin(), substrings[i].end());
- }
- memset (dp, -1, sizeof (dp));
- memset (maxDP, -1, sizeof (maxDP));
- for (int i = 0; i < (int) substrings[1].size(); i++) {
- int msk = substrings[1][i].S;
- dp[1][msk] = __builtin_popcount (msk);
- maxDP[1][msk] = dp[1][msk];
- if (i > 0) {
- int last = substrings[1][i - 1].S;
- maxDP[1][msk] = max (maxDP[1][last], dp[1][msk]);
- }
- }
- for (int i = 2; i <= n; i++) {
- for (int j = 0; j < (int) substrings[i].size(); j++) {
- int msk = substrings[i][j].S;
- string str = substrings[i][j].F;
- auto it = lower_bound (substrings[i - 1].begin(), substrings[i - 1].end(), make_pair (str, msk));
- if (it == substrings[i - 1].begin())
- continue;
- --it;
- int pre = (*it).S;
- dp[i][msk] = __builtin_popcount (msk) + maxDP[i - 1][pre];
- maxDP[i][msk] = dp[i][msk];
- if (j > 0) {
- int lastMsk = substrings[i][j - 1].S;
- maxDP[i][msk] = max (dp[i][msk], maxDP[i][lastMsk]);
- }
- }
- }
- int mx = -1;
- for (int i = 0; i < (int) substrings[n].size(); i++)
- mx = max (mx, dp[n][substrings[n][i].S]);
- cout << mx << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement