opt[i][j]表示第i天在City j的时候能获得的最大收入
payment[i][j] 从City i到City j的花费
getMoney[i][j] 第i天在City j能得到的收入

opt[i][j]=MAX{opt[i-1][j]-payment[j][j]+getMoney[i][j],
             (1<=k<=n),opt[i-1][k]-payment[k][j]+getMoney[i][j]}
初始化条件:
opt[0][1]=0
(1<=j<=n)
opt[1][j]=opt[0][1]-payment[1][j]+getMoney[1][j];

• Re:忘记初始化city1，贡献了一次wa，说下DP思路，大牛的话就直接无视掉好了~~ (22) antonio081014 2010-04-11 04:20:22