всем привет , кто может объяснить решение этой задачи ?
P.S. я прочел разбор , но не понял.
заранее не минусуйте...
# | User | Rating |
---|---|---|
1 | jiangly | 3976 |
2 | tourist | 3815 |
3 | jqdai0815 | 3682 |
4 | ksun48 | 3614 |
5 | orzdevinwang | 3526 |
6 | ecnerwala | 3514 |
7 | Benq | 3482 |
8 | hos.lyric | 3382 |
9 | gamegame | 3374 |
10 | heuristica | 3357 |
# | User | Contrib. |
---|---|---|
1 | cry | 168 |
2 | -is-this-fft- | 165 |
3 | atcoder_official | 161 |
3 | Um_nik | 161 |
5 | djm03178 | 157 |
6 | Dominater069 | 156 |
7 | adamant | 154 |
8 | luogu_official | 152 |
9 | awoo | 151 |
10 | TheScrasse | 147 |
Name |
---|
Писал одному разбор в личку. На английском.
Hello!
Sorry for the delay.
So, the main idea is to count the DPlen, bal — number of valid bracket sequences which have length len and final balance bal.
— DP0, 0 = 1, just empty sequence.
— DPlen, bal = DPlen - 1, bal - 1 (we added ( to all valid sequences of length len - 1) + DPlen - 1, bal + 1 (we added ) to all valid sequences of length len - 1);
Note: Don't forget to care about bounds. In my implementation I use the forward DP style — instead looking the previous values I add current values to next DP states.
Definitions:
— String is 0-indexed array.
— N — length of the string.
— For the given string replace ( with 1 and ) with - 1.
— For the reverse string of given string replace ) with 1 and ( with - 1.
— i-th prefix sum — sum of corresponding values from 0-th index to i-th index.
— i-th suffix sum — sum of corresponding values from N - 1-th index to i-th index.
— Prefix balance (I will call it pref) — minimum of all i-th prefix sums, where 0 ≤ i ≤ N - 1
— Suffix balance (I will call it suff) — minimum of all i-th suffix sums, where 0 ≤ i ≤ N - 1
Valid bracket sequence has the following properties:
— pref ≥ 0.
— suff ≥ 0.
Then we have some observations which I will explain on an example.
Example: ())()((
Prefix sums: {1, 0, - 1, 0, - 1, 0, 1}
Suffix sums: { - 1, 0, - 1, - 2, - 1, - 2, - 1}
pref = - 1.
suff = - 2.
That means that the string p (from the problem description) must have a prefix balance ≥ 1 to make the sequence valid.
Also the string q must have a suffix balance ≥ 2.
Observations:
— Symmetry — the number of valid sequences with length len and prefix balance bal = number of valid sequences with length len and suffix balance bal = DPlen, bal
— If length of p is len then the length of q is n - m - len.
— Balance of p is ≥ pref.
— Balance of q is ≥ suff.
— If we have additional bal balance in p we must have the same additional balance in q.
So, to count the answer we can iterate through all possible lengths and balances of p and add to answer DPlen, pref + bal * DPn - m - len, suff + bal.
If something is not clear just say. :)
Код.