洛谷 5003 跳舞的线 - 乱拐弯

发表于 | 分类于 |

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

设 \(f_{\max / \min,i,j,0 / 1}\) 表示走到了 \((i,j)\)，线的方向是横或纵的最大或最小拐弯次数。
转移很显然： \[\begin{align*} f_{\max,i,j,0} &= \max(f_{\max,i,j - 1,0},f_{\max,i,j - 1,1} + 1) \\ f_{\max,i,j,1} &= \max(f_{\max,i - 1,j,0} + 1,f_{\max,i - 1,j,1}) \\ f_{\min,i,j,0} &= \min(f_{\min,i,j - 1,0},f_{\min,i,j - 1,1} + 1) \\ f_{\min,i,j,1} &= \min(f_{\min,i - 1,j,0} + 1,f_{\min,i - 1,j,1}) \\ \end{align*}\]

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

代码： 

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