Codeforces Round #417 (Div. 2) B. Sagheer, the Hausmeister(DP)

题目链接：Codeforces Round #417 (Div. 2) B. Sagheer, the Hausmeister

题意：

有n层楼，每层有m个房间，每层的两边是楼梯。

现在有一个人站在左下角，这个人必须将这一层的灯关闭后才能去另外一层。

每移动一次需要1分钟，问关闭所有灯需要多少时间。

题解：

考虑DP[i][j]表示当前已经关闭了第i层全部的灯,j=0时表示在这一层的最左边，j=1时表示在这一层的最右边。

然后推上去就行了。最后讨论一下特殊情况。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 
 5 int n,m,l[16],r[16],dp[15][2];
 6 char s[200];
 7 
 8 void up(int &a,int b){if(a>b)a=b;}
 9 
10 int main()
11 {
12     scanf("%d%d",&n,&m);m+=2;
13     F(i,1,n)
14     {
15         l[i]=m,r[i]=1;
16         scanf("%s",s+1);
17         F(j,1,m)if(s[j]=='1'){l[i]=j;break;}
18         for(int j=m;j;j--)if(s[j]=='1'){r[i]=j;break;}
19     }
20     F(i,1,n)F(j,0,1)dp[i][j]=INT_MAX;
21     dp[n][1]=m-1,dp[n][0]=2*(r[n]-1);
22     int cnt=1,ans=INT_MAX;
23     F(i,1,n){if(l[i]==m)cnt=i+1;else break;}
24     for(int i=n-1;i>=cnt;i--)
25     {
26         if(i==cnt)
27         {
28             up(ans,dp[i+1][0]+r[i]);
29             up(ans,dp[i+1][1]+m-l[i]+1);
30         }
31         else
32         {
33             up(dp[i][0],dp[i+1][0]+2*r[i]-1);
34             up(dp[i][0],dp[i+1][1]+m);
35             up(dp[i][1],dp[i+1][0]+m);
36             up(dp[i][1],dp[i+1][1]+2*(m-l[i]+1)-1);
37         }
38     }
39     if(cnt>=n||n==1)ans=r[n]-1;//注意特殊情况
40     printf("%d
",ans);
41     return 0;
42 }

View Code