题解 P5003 【跳舞的线 - 乱拐弯】
引领天下
2018-11-07 18:01:22
其实这题完全没有楼下讲的那么难……我就来解释一下我的思路吧
1. 首先，(i,j)这个点的答案肯定由(i-1,j)和(i,j-1)的答案确定（因为只准往下、往右走）
1. 我设到达(i,j)时的最大拐弯数为f[i][j]，则有
- f[1][1...n]=0
- f[1...n][1]=0
1. 我用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分类讨论实现的
1. 同理可得，$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种可能}$
具体细节看代码：
```cpp
#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');
}
```