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]；