开学前的作文
by Starzxy
首先,光标移动范围不可能超出 $(1,1)-(n,m)$ 的方格。其次,只有 →,↓ 与 Fn 是有效的按键。(很显然吧……
算法一
枚举每一种不同的操作,时间复杂度$O(3^{n+m})$。可以获得10分。
算法二
设 $N[x],x\in${↓ , →}表示按下 $x$ 键后光标行位置的变化。
设 $M[x],x\in${↓ , →}表示按下 $x$ 键后光标列位置的变化。
用 $F[n][m][k_1][k_2]$ 表示光标移动到第 $n$ 行第 $m$ 列最后分别按下的 ↓,→ 或未进行按键操作是 $k_1$ 与 $k_2$,则 $F[n][m][k_1][k_2]=min(F[n-N[k_2]][m-M[k_2]][k_x][k_1],F[n-N[k_1]-N[k_2]][m-M[k_1]-M[k_2]][k_1][k_2])+1$,$k_x$ 为任意操作,$\mathrm{DP}$ 可以做到 $O(nm)$ 的复杂度。可以获得50分。
算法三
对于只有一行或者一列的情况,多枚举一些就能找到规律。(啊啊啊就在右(下)边我要拼命按右(下)按Fn!
可以获得20分,结合算法二可以获得70分。