关灯

题目大意：给定一个$X\times (Y+2)$ 的$01$二维矩阵，规定第一列和最后一列均为$0$,其余均为$0/1$，现规定从$(1,1)$开始，每次只能向上/左/右走，走到每个位置会将$1$变成$0$，问：最少要走多少步才能使这个矩阵全变为$0$

数据范围：$X\le 20,Y\le 100$

思路：用$dp[i][2]$表示从第$i$层的左/右上楼，在当前楼层全$0$后走到最左/右侧所花的步数，用$l$,$r$两个数组维护某一层最左侧和最右侧为$1$的位置

那我们从最顶层开始往下递推看，可以得转移方程：

$dp[i][0]=min(dp[i+1][0]+1+2*r[i],dp[i+1][1]+1+y+1)$

$dp[i][1]=min(dp[i+1][0]+1+y+1,dp[i+1][1]+1+2*(y+1-l[i]))$

维护答案$res=min(dp[i+1][0]+1+r[i],dp[i+1][1]+1+(y+1-l[i]))$

最后记得赋初值就行了

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int x,y;
char s[20][150];
int dp[20][2],l[105],r[105];
int main(){
	cin>>x>>y;
	for(int i=0;i<x; i++){
		scanf("%s",s[i]);
		l[i]=y+1;r[i]=0;
		for(int j=1;j<=y;j++)
			if(s[i][j]=='1'){
				l[i]=min(l[i],j);
				r[i]=max(r[i],j);
			}
	}
	int res=0;
	if(r[x-1]!=0)res=r[x-1];
	dp[x-1][0]=2*r[x-1];
	dp[x-1][1]=y+1;
	for(int i=x-2;i>=0;i--){
		if(r[i]!=0) res=min(dp[i+1][0]+1+r[i], dp[i+1][1]+1+(y+1-l[i]));
		dp[i][0]=min(dp[i+1][0]+1+2*r[i],dp[i+1][1]+1+y+1);
		dp[i][1]=min(dp[i+1][0]+1+y+1,dp[i+1][1]+1+2*(y+1-l[i]));
	}
	cout<<res<<endl;
    return 0;
}