diff options
Diffstat (limited to 'Practical2/report/notation.tex')
| -rw-r--r-- | Practical2/report/notation.tex | 8 |
1 files changed, 5 insertions, 3 deletions
diff --git a/Practical2/report/notation.tex b/Practical2/report/notation.tex index cbbbc1d..0781524 100644 --- a/Practical2/report/notation.tex +++ b/Practical2/report/notation.tex @@ -1,9 +1,11 @@ \section{Notation} \label{sec:notation} -I will write $\bar a = \seq{a_i \mid i<n}$ for the sequence of numbers and $k$ for the number of substrings. I redefine $\round{x}$ to mean `the nearest multiple of $5$ to $x$'. We may define the `round profit' as $\PR(x)=x-\round{x}$. +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$'. -Let $\PM_k(\bar a)$ be the minimal sum of rounded sums of $\bar a$ using $k$ partitions. I will use $\PP_k(\bar a)$ as the `maximum profit' of $\bar a$, that is, $\PP_k(\bar a) = \sum\bar a - \PM_k(\bar a)$. This leads to the term `profit' of a particular partitioning of $\bar a$ and of a particular (sub)string $\bar a'$, for which we need not introduce notation. The profit of a string $\bar a'$ is defined as $\PR(\sum\bar a)$. It is not difficult to see that the profit of a partition is equal to the some of the profits of its members. +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. -We define the gain $G^k_p(\bar a)$ as $\PP_k(\seq{a_i\in\bar a\mid i<p})$ (that is, the maximal profit on $\bar a$'s prefix with length $p$ using $k$ partitions). Lastly, let $S_i^j(\bar a)$ be the sum of all $p_x\in\bar a$ with $i\le x<j$. +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$. |