blob: 07815249341efe2701be5276a41e2a3e63dad4f0 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
|
\section{Notation}
\label{sec:notation}
I will write $\bar a = \seq{a_i \mid i<n}$ for the sequence of numbers and $k+1$ for the number of substrings. I redefine $\round{x}$ to mean `the nearest multiple of $5$ to $x$'.
We may define the `rounding profit' of $x$ as $\PR(x)=x-\round{x}$. The rounding profit of a string $\bar a$ is defined as $\PR(\sum\bar a)$, and the rounding profit of a partition of $\bar a$ is the sum of the rounding profits of its elements.
Let $\PM_k(\bar a)$ be the minimal sum of rounded sums of $\bar a$ using $k+1$ partitions. I will use $\PP_k(\bar a)$ as the `maximum profit' of $\bar a$ using $k+1$ partitions, that is, $\PP_k(\bar a) = \sum\bar a - \PM_k(\bar a)$.
We define the gain $G^k_p(\bar a)$ as $\PP_k(\seq{a_i\in\bar a\mid i<p})$ (i.e., the maximal profit on $\bar a$'s prefix with length $p$ using $k+1$ partitions). Lastly, let $S_i^j(\bar a)$ be the sum of all $p_x\in\bar a$ with $i\le x<j$.
|
