BRKSTRNG - Breaking String
A certain string-processing language allows the programmer to break a string into two pieces. Since this involves copying the old string, it costs n units of time to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order in which the breaks are made can affect the total amount of time used. For example, suppose we wish to break a 20 character string after characters 3, 8, and 10 (numbering the characters in ascending order from the left-hand end, starting from 1). If the breaks are made in left-to-right order, then the first break cost 20 units of time, the second break costs 17 units of time, and the third breaks costs 12 units of time, a total of 49 units of time (see the sample below). If the breaks are made in right-to-left order, then the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, a total of 38 units of time.
The cost of making the breaks in left-to-right order:
thisisastringofchars (original)
thi sisastringofchars (cost: 20 units)
thi sisas tringofchars (cost: 17 units)
thi sisas tr ingofchars (cost: 12 units)
Total: 49 units.
The cost of making the breaks in right-to-left order:
thisisastringofchars (original)
thisisastr ingofchars (cost: 20 units)
thisisas tr ingofchars (cost: 10 units)
thi sisas tr ingofchars (cost: 8 units)
Total: 38 units.
Input
There are several test cases! In each test case, the first line contains 2 integers N (2 ≤ N ≤ 10000000) and M (1 ≤ M ≤ 1000, M < N). N is the original length of the string, and M is the number of the breaks. The following lines contain M integers Mi (1 ≤ Mi < N) in ascending order that represent the breaking positions from the string's left-hand end. Read input till EOF.
(There wont be more than 100 cases)
Output
For each test case, output in one line the least cost to make all the breakings.
Example
Input: 20 3 3 8 10 20 4 2 3 8 10 Output: 37 40
hide comments
|
johann_jpg:
2023-06-06 09:30:29
@prasoonjha1: Wrong answer on Test 4 has to do something with how you use the cin.eof(). the problem there is probably that the testcase contains another empty line or something. Just use an extra check after reading N and M. But still then the time limit is hard. |
|
prasoonjha1:
2023-05-08 16:17:15
I am using knuth's optimization but continuously getting WA at test case 4....anyone got any hint?
|
|
ahmed_57:
2022-11-13 19:51:30
knuth dp optimization |
|
marethyu1:
2019-04-12 00:03:54
Knuth's optimization |
|
kagami_taiga7:
2016-01-19 12:14:51
@mohit hahaha chutiya |
|
mohit:
2016-01-19 12:11:17
nice question :) Last edit: 2016-01-19 14:31:24 |
|
B S Sachin Govind:
2014-12-10 09:04:41
can u please explain how it is 37 ans of first case whil above it is explained as 38 Last edit: 2014-12-10 09:12:03 |
|
|
B S Sachin Govind:
2014-12-09 22:29:48
how to read till eof
|
|
Shafaet:
2013-11-26 13:16:49
@Shaka Shadows: Authors of faster solutions user priority queue, i am not sure how those solutions work, my solution is O(M^2). |
|
Shaka Shadows:
2013-08-30 14:30:12
@Shafaet: Is it possible to solve this with a complexity better than O(M ^ 2)? My ACed solution has that complexity, but the running time is way worse than the other AC so far. |
| Added by: | Shafaet |
| Date: | 2013-08-28 |
| Time limit: | 1s-2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Author: Wei, Qizheng, Source: ZOJ Monthly, June 2007 |
RSS