【语言学习-日语】 《标准日本语-初级上册》复习笔记

助词

1.は：提示主语，做助词时读wa。有时用来表强调。

2.を：

与他动词搭配提示宾语 例：私はご飯をたべる。

与自动词搭配提示经过的地点 例：家を出る。

【算法-动态规划】 四边形不等式优化的证明

四边形不等式

对于形如$f(i,j)=\min \{ f(i,k)+f(k+1,j)+w(i,j)\}$形式的DP，若对于$i \leq i' \leq j \leq j'$，有$w(i',j) \leq w(i,j')$（即区间包含单调性）和$w(i,j)+w(i',j') \leq w(i',j)+w(i,j')$（即四边形不等式），则有：

定理1：f也满足四边形不等式，即$f(i,j)+f(i',j') \leq f(i',j)+f(i,j')$

定理2：记g(i,j)为对f(i,j)最优的k，则决策点g(i,j)满足单调性，即$g(i,j) \leq g(i+1,j) \leq g(i,j+1)$

四边形不等式可以简记为“交错小于包含”。

【数学】笔记：华罗庚对Witt定理的证明

归结的思路相当精彩。

Witt定理

定理：设$A_1,B_1 \in M_m(F),A_2,B_2 \in M_n(F)$都是实对称矩阵，$\begin{pmatrix}A_1 & \\ & A_2 \end{pmatrix}$与$\begin{pmatrix}B_1 & \\ & B_2 \end{pmatrix}$合同，$A_2$与$B_2$合同，则$A_1$与$B_1$合同。

证明的大致思路：分两步，先证若$A_1,B_1$都可逆则成立，再证删去可逆条件也成立。

【算法-其他】照亮房间 思维题

题目大意

顺时针给出一个只由横线和竖线组成的房间的顶点坐标，问你是否能放一盏灯照亮整个房间？($n \leq 100$)

【算法-搜索】POJ3634 circle of debt

万万没想到自己害有写题解的一天QAQ……

题目大意

甲乙丙三个人互相之间有债务关系，并且每个人都有若干张纸币，面值为1,5,10,20,50,100，每人纸币不超过30张，债务和每人的钱数都不超过1000，问最少交换几张纸币就能还清债务？

注明：甲欠乙x元，乙欠丙x元，丙欠甲x元，或者乙欠甲x元，丙欠乙x元，甲欠丙x元，这两种情况也算还清债务。

也许我初三的时候有可能做得出来，但现在肯定是做不出来了……