题解 P5003 【跳舞的线 - 乱拐弯】

其实这题完全没有楼下讲的那么难……我就来解释一下我的思路吧

1. 首先，(i,j)这个点的答案肯定由(i-1,j)和(i,j-1)的答案确定（因为只准往下、往右走）

2. 我设到达(i,j)时的最大拐弯数为f[i][j]，则有

   • f[1][1…n]=0

   • f[1…n][1]=0

3. 我用h[i][j]表示到(i,j)的走向（0表示向右，1表示向下，2表示任意）

   则可以得到转移： $f[i][j]=max(f[i-1][j]+(h[i-1][j]!=1),f[i][j-1]+(h[i-1][j]!=0))$

   为什么用!=而不用==呢？因为是求最大拐弯数，所以能拐我一定拐，!=保证了当上一个点只要不是当前方向就一定拐。

   这也是h数组中2的用处。

   因为不仅要答案，还要求h数组，所以这个max我是用if分类讨论实现的

4. 同理可得，$g[i][j]=min(g[i-1][j]+(k[i-1][j]==0),g[i][j-1]+(k[i][j-1]==1))$，这里的==保证了能不拐我绝对不拐

然后就是一个坑：要先跑一遍，看能不能到。

最后初始化：$f[2…n][2…m]=-(1<<11),g[2…][2…m]=1<<11,h[1…n][1]=1 \text{因为向下走只有1种可能}$

具体细节看代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,f[1005][1005],g[1005][1005],h[1005][1005],k[1005][1005];
char c;
bool v[1005][1005],can[1005][1005];
int check(int i,int j){
    if (can[i-1][j]&&can[i][j-1])return 2;
    else if (can[i-1][j])return 1;
    else return 0;
}//在分类讨论中，判断当从(i-1,j)和(i,j-1)过来且拐弯数相同时哪一种可行
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++){
        cin>>c;
        if (c=='#')v[i][j]=1,can[i][j]=0;//标记为不可走
    }
    can[1][1]=!v[1][1];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        can[i][j]|=can[i-1][j]|can[i][j-1];
        if (v[i][j])can[i][j]=0;
    }
    if (!can[n][m])return !printf ("-1");//看能不能过
    for (int i=2;i<=n;i++)
    for (int j=2;j<=m;j++)f[i][j]=-(1<<11),g[i][j]=1<<11;//初始化
    for (int i=1;i<=n;i++)h[i][1]=k[i][1]=1;
    for (int i=2;i<=n;i++)
    for (int j=2;j<=m;j++)if (can[i][j]){
        if (f[i-1][j]+(h[i-1][j]!=1)>f[i][j-1]+(h[i][j-1]!=0)&&(can[i-1][j]))f[i][j]=f[i-1][j]+(h[i-1][j]!=1),h[i][j]=1;//从(i-1,j)过来可行且更优
        else if (f[i-1][j]+(h[i-1][j]!=1)==f[i][j-1]+(h[i][j-1]!=0))f[i][j]=f[i-1][j]+(h[i-1][j]!=1),h[i][j]=check(i,j);//相同
        else if (can[i][j-1])f[i][j]=f[i][j-1]+(h[i][j-1]!=0),h[i][j]=0;//(i,j-1)更优
        if (g[i-1][j]+(k[i-1][j]==0)<g[i][j-1]+(k[i][j-1]==1)&&(can[i-1][j]))g[i][j]=g[i-1][j]+(k[i-1][j]==0),k[i][j]=1;
        else if (g[i-1][j]+(k[i-1][j]==0)==g[i][j-1]+(k[i][j-1]==1))g[i][j]=g[i-1][j]+(k[i-1][j]==0),k[i][j]=check(i,j);
        else if (can[i][j-1])g[i][j]=g[i][j-1]+(k[i][j-1]==1),k[i][j]=0;//同上
    }
    if (f[n][m]>0)printf ("%d %d\n",f[n][m],g[n][m]);
    else putchar('-'),putchar('1');
}