为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/charrec
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 5 .4中的OI题目Character Recognition的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 问题分析
乍一看有点无从下手。本来想着是统计问题，后来看了北极天南星大牛的题解，发现有最优子结构。所以这题的标准算法是DP。 首先从font.in中把27个字符提取出来，单独构成27个图，称为字符图集。这样是为了处理方便。 设b[i]表示给定图从第i行开始匹配所能得到的最小差距，c[i,j]表示给定图从第i行开始连续匹配j行所能得到的最小差距，dif[i,j,k]表示第i个字符图的第j行与给定图的第k行的差距。
- b[i]:=min(b[i+19]+c[i,19],b[i+20]+c[i,20],b[i+21]+c[i,21])
其中c[i,j]的计算方法：
- j=19：枚举字母。设pre[i]表示字符图前i行匹配的差距，tail[i]表示后i行匹配的差距，则c[i,j]:=min(pre[k]+tail[19-k]).
- j=20：直接枚举字符，统计即可。
- j=21：与j=19相仿。
对于其中涉及到的统计问题，可以从dif[i,j,k]直接获得，避免了很多重复计算
一个小优化：因为并不是所有的状态都会用到，所以可以用记忆化搜索，时间很漂亮。。
分割线-----------------------------------------------------------------------
这题我做了半天 >.<
后来终于发现我对题目理解有误，多了一行或者少了一行是不用计入到差异值之中的 ～
所以上面这位大牛说的 c[i][19] 可以这样算：
先枚举 27 个字母，
在枚举缺的是哪一行，比如当前枚举到缺的是第 13 行，
那么差异值就是 给定图第 i 行与字符图第 i 行 (i <= 12) 的差异值之和 与 给定图第 i 行与字符图第 i + 1 行 (i >= 13) 的差异值之和
c[i][21] 同样做 ~
然后 c[i][j] 算出来了之后，就好 DP 了。
DP 状态表示为： DP[i]
表示匹配到了 给定图 的第 i 行，所得到的最小的差异值，
那么 DP[i] 就可以由 DP[i-19] DP[i-20] DP[i-21] 得到
转移就是这样的：
for i := 1 to 18 do dp[i] := oo ; dp[19] := cost[19][19] ; e[19] := 19 ; dp[20] := cost[20][20] ; e[20] := 20 ; for i := 21 to n do begin dp[i] := oo ; for j := 19 to 21 do if (o[i][j] < 28) and (dp[i-j] + cost[i][j] < dp[i]) then begin dp[i] := dp[i-j] + cost[i][j] ; e[i] := j ; end ; end ;
在转移的时候记录下方案，刚刚算的 cost[i][j] 也去记录方案，然后输出即可 * ^_^ *
Added by Winter Legend
[编辑] 路人
我只能说这题很无聊， 我动规中心那段是
s19=... s20=... s21=... if f[i]>s19 then ... if f[i]>s20 then ... if f[i]>s21 then ...
结果过不了，改为
if f[i]>=s19 then ... if f[i]>=s20 then ... if f[i]>=s21 then ...
得到不同的错误答案，又改为
if f[i]>=s19 then ... if f[i]>s20 then ... if f[i]>s21 then ...
就AC了，害我调试半天
[编辑] 路过的菜鸟
我犯了个很白痴的错误--空格就打空格。。不要打“_”。。汗。。
~~路过的沙茶~~
写了半天模拟。。。T T
//路过的 "If your program does not recognize a particular character, it must output a ? in the appropriate position." 其实答案里面没有?,输出?反而会wa...
