题目链接：
http://codeforces.com/problemset/problem/812/B
题意：
某一个楼有N层，每一层层M+2个房间，第一个房间和最后一个房间表示的是左楼梯和右楼梯。现在管理员处于最底层的左楼梯处，管理员关灯的时候有两个原则：
1.必须要将一层楼的灯全部关闭以后，才可以去上面的楼层。
2.管理员每次移动一个位置的时间均为1S，并且关灯的动作时不算时间的，但是上楼梯算1S。当把灯全部关闭以后，不用再次回到初始的位置。
问管理员移动需要的最短时间。
题解：
比较水的dp，需要一些预处理。
代码：
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define met(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f char s[15+10][100+10]; int mp[15+10][100+10]; int dp[15+10][2];//表示的是当到达I层的时候左右楼梯的最小的时间 struct node { int ans; int pos1,pos2; }num[15+10];//对数据进行处理，处理出每一层所需要花费的时间以及每一层1的开始位置和1的结束位置 int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",s[i]); met(mp,0); for(int i=0;i<n;i++) for(int j=0;j<m+2;j++) mp[i][j]=s[i][j]-'0'; met(num,0); for(int i=0;i<n;i++) { int cnt=0; for(int j=0;j<m+2;j++) { if(mp[i][j]==1) cnt++; } num[i].ans=cnt; } for(int i=n-1;i>=0;i--) { int flag=0; int cnt=num[i].ans; for(int j=0;j<m+2;j++) { if(mp[i][j]==1) { if(!flag) { flag=1; num[i].pos1=j; } cnt--; if(cnt==0) { num[i].pos2=j; break; } } } } // 对于一些特殊情况的判断。 if(n==1) { printf("%d\n",num[0].pos2); return 0; } else if(n==2&&num[0].ans==0) { printf("%d\n",num[1].pos2); return 0; } int pos=0; // 处理出最顶层的位置 for(int i=0;i<n;i++) { if(num[i].ans!=0) { pos=i; break; } } for(int i=0;i<n;i++) { if(num[i].ans==0) { num[i].pos1=m+1; num[i].pos2=0; } } met(dp,inf); // dp的初始化 dp[n-1][0]=num[n-1].pos2*2; dp[n-1][1]=m+1; if(pos==n-1) { printf("%d\n",num[n-1].pos2); return 0; } for(int i=n-2;i>=pos;i--) { if(i!=pos) { dp[i][0]=min(dp[i+1][1]+m+1,dp[i+1][0]+num[i].pos2*2); dp[i][1]=min(dp[i+1][0]+m+1,dp[i+1][1]+(m+1 -num[i].pos1)*2); } else { dp[i][0]=min(dp[i+1][1]+(m+1-num[i].pos1),dp[i+1][0]+num[i].pos2); dp[i][1]=min(dp[i+1][1]+(m+1-num[i].pos1),dp[i+1][0]+num[i].pos2); } } int ans=min(dp[pos][0],dp[pos][1]); if(ans==0) printf("0\n"); else printf ("%d\n",ans+n-1-pos); // 最后还是要加上上楼的时间 }