讨论 / 比较好的动归题
tld 2008-08-20 07:24:00
点我顶贴 收藏 删除
写一下我思路吧:

dp[x1][x2][k]

k--->表示第k步

x1--->表示第1次取值的x坐标

x2--->表示第2次取值的x坐标

想一想:根据k能否求(x1,y1)(x2,y2)

答案是肯定的:y1=k-x1+1 y2=k-x2+1

知道(x1,y1)(x2,y2)后就好办了

dp[x1][x2][k]=

min{ dp[x1][x2][k-1],dp[x1][x2-1][k-1],dp[x1-1][x2][k-1],dp[x1-1][x2-1][k-1]}+sum(x1,y1,x2,y2)

dp[1][1][1]=a[1][1];

#1 swq27@2008-08-20 07:24:00
回复 删除
这是哪一题
#2 Mato完整版@2008-08-20 07:24:00
回复 删除
你说哪道题啊?
查看更多回复
提交回复