всем привет , кто может объяснить решение этой задачи ?
P.S. я прочел разбор , но не понял.
заранее не минусуйте...
# | User | Rating |
---|---|---|
1 | tourist | 3757 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 165 |
3 | adamant | 164 |
4 | TheScrasse | 159 |
5 | maroonrk | 155 |
6 | nor | 154 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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. :)
Код.