\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月7日}

\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*{动态规划，DP}

与分治类似，将原问题分成子问题，但区别在于动态规划的拆分比较复杂，
而动态规划通过记忆表

\section*{矩阵乘法}

给定$p_0,p_1,\ldots,p_n\in Z^+$以及一系列矩阵$A_1,A_2,\ldots,A_n$，
其中$A_i\in R^{p_{i-1}\times p_i}$，要求将计算$A_1A_2\cdots A_n$
的数乘 (scalar multiplication)次数最小

其中，\[{(A_i{A_j})}_{m,n}=\sum_{k=0}^{p_j}\underbrace{A_i(m,k)A_j(k,n)}_{\mathrm {scalar\ multiplication}}\]

实际上，计算这一次数有$2^{\Omega(n)}$种方案，所以暴力枚举是无法解决该问题的

而最后一次乘法将问题拆分为\textbf{独立}的两个子问题，独立是为了证明
算法的正确性；而拆分需要尝试所有的可能解

\begin{algorithm}
    \caption{ChainOrder (s,t)}
    \SetKwFunction{CO}{ChainOrder}
    \uIf{$s=t$}{\KwRet{0}}
    \uElseIf{$s+1=t$}{\KwRet{$p_{s-1}\times p_s\times p_t$}}
    \uElse{
        $ans = \infty$\\
        \For{$i \in  \interval[soft open fences, open right]{s}{t}$}{
            $ans = \min\{ans, $\CO$(s,i) + $\CO$(i+1,t)+p_{s-1}\times p_i\times p_t\}$
        }
        \KwRet{ans}
    }
\end{algorithm}

因为算法中相同的\textsc{ChainOrder} (s,t)可能被调用很多次，可以
将其值存下，方便之后的调用；这需要进行初始化；同时这是自顶向下的
方法

同样也可以考虑自底向上的方法，直接三重循环，不再使用递归调用

\section*{带权的任务调度}

在$[0,T]$之间有$n$个任务，每个任务$j$从$h(j)$开始到$e(j)$结束，
权重为$w_j$，两个任务不能重叠，要求找到最大权重的任务子集

考虑时刻$H$，将原问题拆分成两个子问题，因为不知道$H$的位置，
所以也需要枚举$H$

\end{document}
