\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\setlength{\headheight}{0pt}
\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
        \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年11月2日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows, positioning}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\begin{document}

\textbf{Q1.}

用数组 $dp[i][j]$ 表示长为 $i$ 的序列中最大值为 $j$ 的满足限制
增性质的序列数目，则有如下递归式

\[dp[i][j]=\begin{cases}
        1,                              & j=1            \\
        dp[i-1][j-1]+j\cdot dp[i-1][j], & 1<j\leqslant i \\
        0,                              & j>i
    \end{cases}\]

将 $dp[i][j]$ 从 $i=1,j=1$ 到 $i=n,j=n$ 逐次计算，得到
$dp[n][n]$，最终所求结果为 $\sum_{j=1}^{n}dp[n][j]$.

因为递归过程中，每个值的计算只需 $O(1)$，一共 $O(n^2)$ 个值要计
算，最终结果时间复杂度为 $O(n)$，因此总的时间复杂度为 $O(n^2)$.

\hrulefill\medskip

\textbf{Q2.}

用数组 $dp[i][j]$ 表示从第 $i$ 个字符到第 $j$ 个字符对应划分的
最高质量分值，有递归式

\[dp[i][j]=\begin{cases}
        q(x_i),                                                                                                     & i=j \\
        \max\left(q(x_{i}x_{i+1}\cdots x_j),\underset{i\leqslant k<j}{\max}\left(dp[i][k]+dp[k+1][j]\right)\right), & i<j
    \end{cases}\]

计算得到 $dp[1..n][1..n]$ 的值，最终只需输出 $dp[1][n]$ 即可.

因为每个值的计算为 $O(n)$，一共 $O(n^2)$个值要计算，所以总的时
间复杂度为 $O(n^3)$.

\hrulefill\medskip

\textbf{Q3.}

用数组 $dp[i][j]$ 表示在第 $i$ 年结束的时候选择副业 $j$ 最大的
积蓄，有递归式

\[dp[i][j]=\begin{cases}
        p_1,                                                                                                              & i=1\land j=1     \\
        -\infty,                                                                                                          & i=1\land j\neq 1 \\
        \max\left(dp[i-1][j]+p_j,\underset{k\neq j\land dp[i-1][k]\geqslant c_j}{\max}\left(dp[i-1][k]-c_j\right)\right), & i>1
    \end{cases}\]

同时用数组 $b[i][j]$ 表示第 $i$ 年结束的时候选择副业 $j$ 取最大
积蓄时，第 $i-1$ 年应该选择的副业下标，有递归式

\[b[i][j]=\begin{cases}
        k, & \mbox{如果 dp[i][j] 由 dp[i-1][k] 决定} \\
        j, & \mbox{如果 dp[i][j] 由 dp[i-1][j] 决定}
    \end{cases}\]

计算得到 $dp[m][1..n]$，最终所求积蓄最大值为 $\underset{1\leqslant j\leqslant n}{\max}(dp[m][j])$.

最佳的选择方案是令 $t=\underset{1\leqslant j\leqslant n}{\arg\max}(dp[m][j])$，
将 $t$ 加入一个数组，接着往回回溯，循环将 $b[i][t]$ 放在数组中 $t$
的前面，并将 $t$ 赋值为 $b[i][t]$，$i$ 赋值为 $i-1$，直到
$i=1$ 为止，数组中的顺序就是应该选择副业的顺序.

动态规划中两个数组都是 $O(n^2)$ 的大小，求每个值只需考虑 $dp$
数组中的值，每个值需要 $O(n)$，动态规划时间复杂度为 $O(n^3)$，
而求最终方案的时间复杂度为 $O(n)$，因此总的时间复杂度为 $O(n^3)$.

\hrulefill\medskip

\textbf{Q4.}

引入 $m_0=-\infty$，使用数组 $dp[i]$ 表示在 $m_i$ 处开摊的最大
收益，有递归式

\[dp[i]=\begin{cases}
        0,                                                       & i=0 \\
        \underset{j<i\land m_i-m_j\geqslant k}{\max}(dp[j])+p_i, & i>0 \\
    \end{cases}\]

同时用 $b[i]$ 记录每个 $dp[i]$ 由哪一个摊决定，即 $b[i]=\underset{j<i\land m_i-m_j\geqslant k}{\arg\max}(dp[j])$.

计算得到 $dp[1..n]$ 后，取最大值即可，然后令 $t=\underset{1\leqslant i\leqslant n}{\arg\max}dp[i]$，
将 $t$ 加入最终结果的数组，接着往回回溯，循环将 $b[t]$ 放在结果
数组中 $t$ 的前面，将 $t$ 赋值为 $b[t]$，直到 $b[t]=0$，则所有
在结果数组中的值就是应该开摊的下标.

两个动态规划数组大小为 $O(n)$，求每个值的求值复杂度为 $O(n)$，
动态规划时间复杂度为 $O(n^2)$，求方案时间复杂度为 $O(n)$，因此
总的时间复杂度为 $O(n^2)$.

\end{document}