首页 > 代码库 > #417(div2) B - Sagheer, the Hausmeister

#417(div2) B - Sagheer, the Hausmeister

题意:输入n,m,代表n层楼,每层有m个房间,左右都有2个楼梯且为0,我们最开始在左下,如果当前楼层没1,那么可以直接向上走,也可以走过去然后走回来,也可以一直走,但向上只能在最左或者最右,问把所有1变成0,要多久,移动一个花费1.

思路:我们可以记录每一层最左边和最右边的1在哪个位置,当前在左边楼梯判断是走到最右边短,还是走到最右边那个1+往回走短;当前在右边楼梯同理。最上面一层需特别处理,我只要走到最后一个1那里就行,没必要走到楼梯那里,还有最上面几层没1

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 char a[20][105];
 5 int dp[20][105];
 6 int b[20];
 7 int c[20];
 8 
 9 int main(){
10     int n,m;
11     scanf("%d%d",&n,&m);
12     m=m+2;
13     for(int i=1;i<=n;i++)
14         scanf("%s",a[i]+1);
15     for(int i=1;i<=n;i++)
16         for(int j=m;j>=1;j--)
17         if(a[i][j]==1) {
18             b[i]=j;break;
19         }
20     for(int i=1;i<=n;i++)
21     for(int j=1;j<=m;j++){
22         if(a[i][j]==1){
23              c[i]=j;break;
24         }
25     }
26     if(b[n]==0) {
27         dp[n][1]=1;dp[n][m]=1;
28     }
29     else {
30         dp[n][1]=b[n]+b[n]-1;
31         dp[n][m]=m;
32     }
33    // cout<<dp[n][1]<<" "<<dp[n][m]<<endl;
34     for(int i=n-1;i>=2;i--){
35         dp[i][1]=dp[i+1][1]+1;
36         dp[i][m]=dp[i+1][m]+1;
37         if(b[i]==0) continue;
38         int l=dp[i][1];
39         int r=dp[i][m];
40         dp[i][m]=min(l+m-1,r+m-c[i]+m-c[i]);
41         dp[i][1]=min(r+m-1,l+b[i]*2-2);
42     }
43         dp[1][1]=dp[2][1]+1;
44         dp[1][m]=dp[2][m]+1;
45         if(b[1]!=0&&n!=1){
46              cout<<min(dp[1][1]+b[1]-1-1,dp[1][m]+m-c[1]-1)<<endl;return 0;
47         }
48         for(int i=1;i<n-1;i++){
49             if(b[i]==0&&b[i+1]!=0){
50                 dp[i+1][1]=dp[i+2][1]+1;
51                 dp[i+1][m]=dp[i+2][m]+1;
52                // cout<<i<<endl;
53                 cout<<min(dp[i+1][1]+b[i+1]-1-1,dp[i+1][m]+m-c[i+1]-1)<<endl;
54                 return 0;
55             }
56         }
57     if(b[n]==0)
58     cout<<0<<endl;
59     else
60         cout<<b[n]-1<<endl;
61     return 0;
62 }

 

#417(div2) B - Sagheer, the Hausmeister