洛谷 5003.跳舞的线 - 乱拐弯

十分 trival 的一道 DP……
状态很显然。

fmax/min,i,j,0/1f_{\max / \min,i,j,0 / 1} 表示走到了 (i,j)(i,j),线的方向是横或纵的最大或最小拐弯次数。
转移很显然:

不过这样子转移可能会造成在起始点拐弯的情况,把最大值减一即可。

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1e3;
const int N = 1e3;
int m,n,a[M + 5][N + 5];
int f[2][M + 5][N + 5][2];
int main()
{
memset(f[0],0x3f,sizeof f[0]),memset(f[1],-0x3f,sizeof f[1]);
scanf("%d%d",&m,&n);
char ch;
for(register int i = 1;i <= m;++i)
for(register int j = 1;j <= n;++j)
scanf(" %c",&ch),a[i][j] = ch == '#';
if(!a[1][1])
f[0][1][1][0] = f[0][1][1][1] = f[1][1][1][0] = f[1][1][1][1] = 0;
for(register int i = 1;i <= m;++i)
for(register int j = 1;j <= n;++j)
if(((i ^ 1) || (j ^ 1)) && !a[i][j])
f[0][i][j][0] = min(f[0][i][j - 1][0],f[0][i][j - 1][1] + 1),
f[0][i][j][1] = min(f[0][i - 1][j][0] + 1,f[0][i - 1][j][1]),
f[1][i][j][0] = max(f[1][i][j - 1][0],f[1][i][j - 1][1] + 1),
f[1][i][j][1] = max(f[1][i - 1][j][0] + 1,f[1][i - 1][j][1]);
if(min(f[0][m][n][0],f[0][m][n][1]) == 0x3f3f3f3f)
puts("-1");
else
printf("%d %d\n",max(f[1][m][n][0],f[1][m][n][1]) - 1,min(f[0][m][n][0],f[0][m][n][1]));
}