Hihocoder #1527 : 快速乘法 DP

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 1e6+10, M = 1e3+20,inf = 1e9,mod = 1e9+7;

char a[N];
int dp[N][2],n;
int main() {
    scanf("%s",a+1);
    n = strlen(a+1);
    a[n+1] = ‘0‘;
    dp[0][0] = -1,dp[0][1] = 1;
    for(int i = 1; i <= n+1; ++i) dp[i][0] = inf, dp[i][1] = inf;
    for(int i = 0; i <= n; ++i) {
        if(a[i+1] == ‘1‘) {
            dp[i+1][0] = min(dp[i+1][0],dp[i][0]+2);
            dp[i+1][1] = min(dp[i+1][1],dp[i][1]);
            dp[i+1][0] = min(dp[i+1][0],dp[i][1]+2);
        }
        else {
            dp[i+1][0] = min(dp[i+1][0],dp[i][1]+2);
            dp[i+1][0] = min(dp[i+1][0],dp[i][0]);
            dp[i+1][1] = min(dp[i+1][1],dp[i][0]+2);
            dp[i+1][1] = min(dp[i+1][1],dp[i][1]+2);
        }
    }
    printf("%d\n",max(0,(dp[n+1][0])));
    return 0;
}