T1 JZOJ5535. 登机(board)
比赛时
一在题目列表里看到题目标题，就热血沸腾了，不知道为什么，老师居然放了一道之前做过的题目。我清楚地记得这题是DP，于是很快码了出来。讲一讲我的思路，让你划分区域使乘客的登机难度总和最少，很容易可以看出是DP，我们就试着表示出阶段和状态，我们设(f_{i,j})表示当前在第(i)到第(i+1)行划分区域，划分了(j)次的最小登机难度。那么我们就考虑一下转移，设(k)表示上一次划分区域的地方，那么从第(k+1)～(i)行是我们新划分出来的区域，那么他对答案的贡献在第(i+1)～(s)行，我们断开以后就不再影响后面的所有行。于是，就要想一个方法，可以快速求出某几个连续的行对后面几个连续的行的贡献，我们设(a_{i,j})表示第(i)行对第(j)行的贡献，我们可以对这个数组进行二维前缀和，这个相信大家都会，得到一个数组(sum_{i,j})就可以轻松的求出贡献了。设当前划分区域的位置为(i)，已经划分了(j)次，上一次划分的位置为(k)，状态转移方程为(f_{i,j}=min(f_{k,j-1}-(sum_{i,s}-sum_{i,i}-sum_{k,s}+sum_{k,i}),f_{i,j}))，初值：(f_{0,0}=sum_{s,s})
之后
我的思想稍微想复杂的一点，不过也差不多
T2 JZOJ5536. 游戏
题目大意
给出一个(W×H)的矩阵，要你用(w×h)的小纸片去覆盖它，小纸片的边与大矩阵平行，且长宽对应（不能旋转(90°)），使大矩 阵不能再被一张小纸片覆盖，求最小需要多少张小纸片。
比赛时
这题我也做过。这是一道很简单的结论题。这里我们设(n=h),(m=w)，避免误解。我们很容易想到，一张(n*m)的小纸片，他能覆盖的面积是(2n*2m)，那么很容易推出来一个公式：(ans=((W/m+1)/2)*((H/n+1)/2))，为什么要(+1)呢，主要是避免特殊情况的余数影响答案（同学们可以在草稿纸上画一画），那要是整除了呢，那也不会影响答案。
之后
同学们的另一个公式：(ans=(lfloor frac{W-m}{2w} floor+1)*(lfloor frac{H-n}{2h} floor+1))