~/Desktop/uva10157.tex.html
\documentclass[slidestop,compress,mathserif,xcolor=dvipsnames]{beamer}
\usepackage{pgfpages}
\usetheme{Berlin}
\usecolortheme{seahorse}
\setbeamercolor{section in head/foot}{fg=white,bg=gray!20!black}
\setbeamertemplate{items}[ball]
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{footline}{}
\usepackage{graphicx}
\usepackage{booktabs}
\let\Tiny=\tiny
\usepackage{fontspec}
\setmainfont{WenQuanYi Micro Hei}
\setsansfont{WenQuanYi Micro Hei Mono}
\setmonofont{WenQuanYi Micro Hei Mono}
\XeTeXlinebreaklocale "zh"
\XeTeXlinebreakskip = 0pt plus 1pt
\begin{document}
\setbeamerfont{subsection in sidebar}{size=\tiny}
\setbeamerfont{title in sidebar}{size=\tiny}
\title{\fontsize{28}{35}\selectfont UVA 10157\\ \fontsize{14pt}{20pt}\selectfont Expression}
\institute{}
\frame{\titlepage}
\section{題意}
\subsection{}
\begin{frame}
\frametitle{題意1}
\uncover<1-> {給你 n 和 d ，你的任務是找出長度為 n，且深度為 d 正確之括號表示式共有多少個。\\}
\uncover<2-> {\vspace{\baselineskip}}
\uncover<2-> {令 X 表示正確的括號表示式。X 的內容為僅含 '(' 和 ')' 的字串。定義如下：\\}
\begin{itemize}
\uncover<3-> {\item 空字串屬於 X。\\}
\uncover<4-> {\item 假如 A 屬於 X ，那麼 (A) 也屬於 X。\\}
\uncover<5-> {\item 假如 A 和 B 都屬於 X ，那麼 AB 也屬於 X。\\}
\end{itemize}
\end{frame}
\subsection{}
\begin{frame}
\frametitle{題意2}
\uncover<1-> {令 E 是一個正確的括號表示式（因此 E 屬於 X）。\\}
\uncover<2-> {\vspace{\baselineskip}}
\uncover<2-> {E 的長度為字串的長度。\\}
\uncover<3-> {\vspace{\baselineskip}}
\uncover<3-> {而 E 的深度 D(E) 被定義如下：\\}
\uncover<4-> {\vspace{\baselineskip}}
\uncover<4-> {$ D(E)=\left\{
\begin{aligned}
& 0 \qquad 如果 E 是 \varnothing \\
& D(A)+1 \qquad 如果 E = (A), 並且 A\in{X} \\
& max(D(A),D(B)) \qquad 如果 E = AB, 並且 A,B\in{X}
\end{aligned}
\right.$}
\end{frame}
\section*{Input and Output}
\begin{frame}
\frametitle{Input and Output}
Input \\
6 2\\
300 150\\
Output \\
3 \\
1 \\
\end{frame}
\section{思考路線}
\subsection{}
\begin{frame}
\frametitle{要用何種演算法？}
\begin{itemize}
\uncover<1->{\item{DP}}
\end{itemize}
\end{frame}
\section{解題方法}
\subsection{}
\begin{frame}
\frametitle{遞迴公式}
\uncover<1->{$ F(n,d)=\left\{
\begin{aligned}
& 1 \ if\ n=0\ \\
& \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise
\end{aligned}
\right.$\\ \vspace{\baselineskip}}
\uncover<2->{F(n,d)之值為長度n的情況，深度不超過d之正確括號總數\\ \vspace{\baselineskip}}
\uncover<3->{因此，F(n,d)-F(n,d-1)便是長度n深度為d的正確括號總數 \\ \vspace{\baselineskip}}
\end{frame}
\begin{frame}
\frametitle{遞迴公式想法部份}
\uncover<1->{$ F(n,d)=\left\{
\begin{aligned}
& 1 \ if\ n=0\ \\
& \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise
\end{aligned}
\right.$\\ \vspace{\baselineskip}}
\uncover<1->{令E是一個長度為n深度為d之合法的表達式，且不為$\varnothing$,\\
而A、B為合法表達式 \\ \vspace{\baselineskip}}
\uncover<2->{E=(A)B \\ \vspace{\baselineskip}}
\uncover<3->{根據上式可得知，\\A的深度等於d-1或B的深度等於d，且A的長度加B的長度為n-2 \\
\vspace{\baselineskip}}
\end{frame}
\begin{frame}
\frametitle{遞迴公式實踐}
\uncover<1->{根據上一張投影片的想法，\\便可以得知，任意一個不為$\varnothing$的E都可拆成(A)B且不重覆，\\ \vspace{\baselineskip}}
\uncover<2->{$ F(n,d)=\left\{
\begin{aligned}
& \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}
\end{aligned}
\right.$ \\ \vspace{\baselineskip}}
\uncover<3->{最後加上空集合後，得到，\\ \vspace{\baselineskip}}
\uncover<4->{$ F(n,d)=\left\{
\begin{aligned}
& 1 \ if\ n=0\ \\
& \mathop{\sum_{k=0}^{n-2}}_{k\;is\;even} F(k,d-1)\times{F(n-k-2,d)}\;otherwise
\end{aligned}
\right.$\\ \vspace{\baselineskip}}
\end{frame}
\begin{frame}
\frametitle{Result DP table}
\begin{tabular}{c||c|c|c|c|c|c|c|c|c|c}
{n$\setminus$d}&\textbf{0}&\textbf{1}&\textbf{2}&\textbf{3}
&\textbf{4}&\textbf{5}&\textbf{6}&\textbf{7}&\textbf{8}&\textbf{9}\\
\hline
\hline
\textbf{0}&1&1&1&1&1&1&1&1&1&1 \\
\hline
\textbf{2}&0&1&1&1&1&1&1&1&1&1 \\
\hline
\textbf{4}&0&1&2&2&2&2&2&2&2&2 \\
\hline
\textbf{6}&0&1&4&5&5&5&5&5&5&5 \\
\hline
\textbf{8}&0&1&8&13&14&14&14&14&14&14 \\
\hline
\textbf{10}&0&1&16&34&41&42&42&42&42&42\\
\end{tabular}
\end{frame}
\end{document}
PDF：UVA 10157 Expression(Result)
