codeforces Relay Race

本文从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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 310
#define INF 0x3f3f3f3f

int n,dp[N*2][N][N],a[N][N];

int Max(int a,int b,int c,int d){
int p = a > b ? a : b;
int q = c > d ? c : d;
return p > q ? p : q;
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d",&a[i][j]);
for(int i = 1; i <= 2*n; i++)
for(int j = 0; j <= n; j++)
for(int k = 0; k <= n; k++)
dp[i][j][k] = -INF;
dp[1][1][1] = a[1][1];
for(int i = 2; i <= 2*n-1; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; 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]);
int ca = i + 1 - j;
int cb = i + 1 - k;
int cnt = 0;
if(1 <= ca && ca <= n){
dp[i][j][k] += a[j][ca]; cnt++;
}
if(1 <= cb && cb <= n){
dp[i][j][k] += a[k][cb]; cnt++;
}
if(cnt == 2 && j == k)
dp[i][j][k] -= a[j][ca];
}
printf("%d\n",dp[2*n-1][n][n]);
}
return 0;
}