本文从WordPress迁移而来, 查看全部WordPress迁移文章
http://codeforces.com/contest/214/problem/E
经典DP
一个人a在(1,1)一个人b在(n,n)每个时刻都是同时走,a只可以向右下走,b只可以向左上走,a的目的地是(n,n),b的目的地是(1,1),每个格子有价值(可正可负),如果一个格子被走了两次价值只算一次,要两人的总价值最大
问题转化为两人都在(1,1)走向(n,n),这个转化是显然的
(假设按题意走出了一条最大价值的路,那完全可以两人都从(1,1)开始走,同样可以走出这条路)
设dp[i][j][k],走出了第i步后,a在第j列,b在第k列,所得到的最大价值
只需要记录列即可,因为a和b所在的行,是可以根据步数和当前所在列算出来的
a所在列:ca = i + 1 - j
b所在列:cb = i + 1 - k
所以如果j = k ,那么两人一定在同一个位置
专题就比较容易写了
dp[i][j][k] = Max(dp[i-1][j-1][k],dp[i-1][j-1][k-1],dp[i-1][j][k-1],dp[i-1][j][k]);
另外加上当前所在方格的价值
dp[i][j][k] += (a[j][ca] + a[k][cb]);
这里注意,并不是每次计算出来的ca和cb都是合法的
加之前要先判断合法性(有些AC程序没有判断合法性也加上去,是不严谨的)
当然要判断是否同一个方格
if(j == k) dp[i][j][k] -= a[j][ca]; //减去一个
1 |
|