jhjfbsbfkbjfnfnfjfj's blog

Cow and Message
By jhjfbsbfkbjfnfnfjfj, history, 5 years ago, In English

Can anyone please help me explain the solution? https://codeforces.net/problemset/problem/1307/C

ll dp[27][27] = {0}, cnt[27] ={0};
ll ans = 0;
for (ll i = 0; i < str.length(); ++i) {
    for (ll j = 0; j < 26; ++j)
    dp[str[i] - 'a'][j] += cnt[j]; //what are we calculating using this dp and how 
    cnt[str[i] - 'a']++;
}

for (ll i = 0; i < 26; ++i) {
    ans = max(ans, cnt[i]);
    for (ll j = 0; j < 26; ++j)
        ans = max(ans, dp[i][j]);
}

pf1(ans);
  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Let me define the DP in terms of characters(there are only 26 characters):

character at ith => x, character at jth => y.

(only for easy to understand) dp[x][y] => this means, how many strings forms of length 2 when combining characters "xy" by only using that much part => [0.....i].

Ex: aabbaabccbb, suppose I'm at index(i)= 7, so I can use only [0...7], dp['a']['b'] => 8, so there will be 8-string of "ab" in [0...7] section.

So, we have to represent the characters in terms of integers. that's why we have done => str[i]-'a'.

Then, for the best ans, you have to take the maximum.

So, you can dry run your code on : "abaabbcccbcc"

→ Reply