USACO 到了 1.3.3

    USACO 1.3.2 里的 Calf flac 和 A Game 用掉了很多时间,前一个 Submit 了 22 次,后一个 Submit 了 13 次。 Calf Flac 其实就是求回文串,但是算法比较独特,经过同学提醒,终于过了。A Game 我知道是 DP,但是我自己编的 DP 怎么样都不对,原来的状态转移方程:f[t,p]=max(f[t-1,p]+d[t-1],f[t,p-1]+d[t+p])(对A),f[t,p]为从t开始,长度为p的数据中 A 相对于 B 的最大优势,d[i]为这些数,但是这样转移第六个点就是错,怀疑是算法问题。想下来,应该是对方认为本方会按照最差的走法走,这是一个问题。原来是t从大到小推,后来改成t从小到大推,但还是错,而且问题严重~ 最后改成了f[t,p,1]=max(f[t,p-1,2]+d[p],f[t+1,p,2]+d[t]),f[t,p,1]表示这时本方在区间[t,p]能得到的最大分数(参照OIBH,Thanks to HenryBag),终于 AC 了~ 这题有16个点~    USACO 1.3.3 似乎是关于二进制的,还没有好好看过。 Old Blog Link: http://computer.mblogger.cn/henryhu/posts/39438.aspx