ZJU/ZOJ 1206 Win the Bonus 解题报告

题目大意是给出m个长度为3的字串，用0-9组合成长度为n的字串，如果字串中能够匹配这m个字串则能够得到相应的加/减分。求得分最高的字串，当得分相同时输出字串对应数值最小的。

用f[i,j]表示匹配到第i个字符，第i位和第i+1位组成的字串为j时的最高得分。状态转移方程是f[i,k*10+j div 10]=max(f[i,k*10+j div 10],f[i+1,j]+v[k*100+j])(0<=k<=9,0<=j<=99);k即第i位上的数，j即第i+1位和i+2位上的数，v[k*100+j]即第i位到第i+2位所组成的三位字串的得分。用一个数组记录下f[i,k*10+j div 10]是由f[i+1,j]变化而得，最后从max(f[1,j])（当有多个最大值时，j取最小值）顺推即可得到所求字串。

1663079    2008-10-10 23:18:07     Accepted    1206    FPC    470    4924    IwfWcf@LZOI