\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{hyperref}
\usepackage{interval}
\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}

\geometry{left=2.5cm,right=2.5cm,headsep=1cm,bottom=2cm,footnotesep=2cm,headheight=13pt}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{\ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年4月14日}

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

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

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{automata, positioning, arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题1.\arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

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

\lstset{basicstyle=\ttfamily}

\begin{document}

\section*{最优二叉搜索树}

依然可以使用动态规划的方法求解，固定根之后，只需考虑子问题的最优解，
而子问题的最优解同样可以作为不同根时的最优解

由于二叉搜索树的特殊性质，不同根节点的时候只需考虑右子树

BST，上有叶节点$d_0,d_1,\ldots,d_n$，非叶节点$k_1,d_2,\ldots,k_n$，
设最优为$T$，右子树$T'$
有
\begin{align}
    E&=\sum_{i=1}^{n}{p_i}\ \rm{depth}(k_i)+\sum_{i=0}^{n}{q_i}\ \rm{depth}(d_i)\nonumber\\
    &=\sum_{i=1}^{r}{p_i}\ \rm{depth}(k_i)+\sum_{i=r+1}^{n}{p_i}\ \rm{depth}(k_i)+\sum_{i=0}^{r-1}{q_i}\ \rm{depth}(d_i)+\sum_{i=r}^{n}{q_i}\ \rm{depth}(d_i)    
\end{align}

上式中二四两项为右子树对深度的贡献，其除了在右子树中的深度之外，
还要加上右子树在原树上的深度，即每个节点需要加上1，而这个概率与
根节点有关，因此子问题的最优解即为原问题的最优解

算法时间复杂度为$O(n^3)$，因为需要三重循环；可以改进为$O(n^2)$

\section*{贪心算法}

除去有效地找出优化问题解，也可以找出近似解

与动态规划不同，贪心算法不枚举决策，每次选取当前最优解，需要证明
局部最优解可以给出全局最优解；但贪心算法并不总能给出最优解，不过
总能给出一个不太差的解

\section*{区间调度问题}

动态规划可以求解带权区间调度问题，但效率不高。使用贪心算法可以更
快地解决这一问题。

但问题来到了，怎样贪心，一种是开始时间最早，一种是结束时间最早，
可以证明，结束时间最早的方法可以给后续问题提供更大的空间，因此应
每次选择结束时间最早的任务。

\begin{theorem}
    对于每个调度问题的子问题$S$，令$a_1$为最早结束时间的任务，那么
    $a_1$在$S$的某一个最大可行解OPT中
\end{theorem}

\begin{proof}
    设$OPT=\{a_0,\ldots\}$，其中$a_0$是第一个任务，
    我们只要证明$OPT'=OPT\backslash \{a_0\}\bigcup\{a_1\}$
    而这个过程中，只需对$a_0,a_1$结束时间比较分类讨论即可
\end{proof}

因此只要对每个任务按结束时间进行排序，每次只需找到第一个开始时间在
前一个结束时间之后的加入集合，更新结束时间，直到扫到最后一个任务，
这样就可以给出一个最优的解集

时间复杂度为排序时间$O(n\log n)$

\section*{最大连续子序列求和}

规定如果序列中全为负数，那么最大连续子序列求和为零。

贪心算法，每次如果前一个求和大于零，则保留，否则从现在开始求和，
输出每次求和与最大值比较最后的最大值

相比贪心算法，空间复杂度更低

\section*{哈夫曼编码}



\end{document}
