{CF812}

链接：CF812
好久之前做的，掉了100多-_-||
太忙了今天才来补题。。。。。。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5 
 6 int dp[20][2];
 7 int li[20],ri[20];
 8 int ex;
 9 int n,m;
10 
11 int main()
12 {
13     scanf("%d%d",&n,&m);
14     m+=2;
15     int up=-1;
16     memset(li,0x3f3f,sizeof(li));
17     for(int i=n;i>=1;i--)
18     {
19         ex=0;
20         for(int j=0;j<m;j++)
21         {
22             int x;
23             scanf("%1d",&x);
24             if(x==1)
25             {
26                 li[i]=min(li[i],j);
27                 ri[i]=max(ri[i],j);
28                 ex++;
29             }
30         }
31         if(ex) up=max(up,i);
32         else{
33             li[i]=m-1;
34             ri[i]=0;
35         }
36     }
37     if(up==-1)
38     {
39         puts("0");
40         return 0;
41     }
42     if(up==1)
43     {
44        printf("%d
",ri[1]);
45        return 0;
46     }
47     dp[1][0]=ri[1]*2;
48     dp[1][1]=m-1;
49     for(int i=2;i<up;i++)
50     {
51         dp[i][0]=1+min(dp[i-1][0]+ri[i]*2,dp[i-1][1]+m-1);
52         dp[i][1]=1+min(dp[i-1][0]+m-1,dp[i-1][1]+(m-1-li[i])*2);
53     }
54     int ans=min(dp[up-1][0]+ri[up],dp[up-1][1]+m-1-li[up])+1;
55     printf("%d
",ans);
56 
57 }