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;
}