CodeForces - 812B [DP]

这道题一开始以为是有规律的的， 想通过最大区域的0来计算，然后用bfs来解决，但是写到一半又发现思路错了，最后还是学长提醒我用dp思路去做，纪录最右和最左的点，dp已经很久没做了，看了网上其他题解才明白要怎么去维护那些状态，里面有几个点需要注意一下：

1.所有的数都为0

2.最下面楼层的dp方式不一样

3.每次dp要保存前一个的状态 因为下一次会变化

AC代码：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int dp[20][110];
char mapp[20][110];
int n,m;
int x,y;

int main() {
	scanf("%d%d",&n,&m);
	x = -1;
	y = -1;
	for(int i = 1; i <= n; i++) {
		scanf("%s",mapp[i]+1);
		if(x != -1 && y != -1) {
			continue;
		}
		for(int j = 1; j <= m+2; j++) {
			if(mapp[i][j] == '1') {
				x = i;
				y = j;
				break;
			}
		}
	}
	//x纪录的是最上面没有关灯的层数
	if(x == -1 && y == -1) {
		printf("0\n");
	} 
	else {
		int l, r;
		memset(dp, INF, sizeof(dp));
		dp[n][1] = 0;
		for(int  i = n; i > 0; i--) {
			dp[i][1] = min(dp[i][1], dp[i+1][1] + 1);
			dp[i][m+2] = min(dp[i][m+2], dp[i+1][m+2] + 1);
			l = 0;
			r = 0;
			for(int j = 2; j <= m+1; j++) {
				if(mapp[i][j] == '1') {
					if(!l) {
						l = j;
					}
					r = j;
				}
			}
			int w = dp[i][1];//记录
			if(r) {
				dp[i][1] = min(dp[i][1] + 2*(r-1), dp[i][m+2]+m+1);
				//1 到最右边的 5 来回就是（5-1）*2 = 8 步数
			}
			if(l) {
				dp[i][m+2] = min(dp[i][m+2] + 2*(m+2-l), w+m+1);
				//最右的m+2位置到最左的位置为 （（m+2） - l）*2 步数
				// 这里的w是之前标记的dp【i】【1】 因为上一个判断会让这个值发生变化
			}
		}
		l = 0, r = 0;
		for(int i = 1; i <= m+2; i++) {
			if(mapp[x][i] == '1') {
				if(!l) {
					l = i;
				}
				r = i;
			}
		}
		int ans = min(dp[x+1][1] + r, dp[x+1][m+2] + (m+2-l) + 1);
		if(x == n) {
			ans = r - 1;
		}
		printf("%d\n",ans);
	}
	return 0;
}