CS Academy Lightbulbs

リンク : https://csacademy.com/contest/archive/task/lightbulbs/statement/

問題概要

01から成る文字列が入力される。i番目が0の場合電球iがついてなくて、i番目が1の場合電球iがついているとする。電球iの操作できる条件が電球i+1がついていて、電球i+2,i+3,i+4...がすべて消えているときである。このとき、すべての電球を消すための最小回数を求めよ。

解説

1のとき、1回、10のとき、3回、100のとき、7回...1と0がn-1個のとき、2ⁿ-1回必要ということが実験するとわかる。そこでdp[i][j]を後ろからi番目の電球がjであり(j=0,1)、iより後ろが全部消えているときの最小回数とする。すると遷移は
if(i番目の状態が0)
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1]+1(i番目を消す)+{(2ⁱ)-1}(i-1番目を消す)
else
dp[i][1]=dp[i-1][0];
dp[i][0]=dp[i-1][1]+1+{(2ⁱ)-1}(上と同様)
で、実装できる。
n<=50に騙されてどうしようかわからず公式解説よんだ・・・

LL dp[60][2];
string str;
int main() {
    cin >> str;
    reverse(str.begin(), str.end());
    dp[0][str[0]-'0'] = 0;
    dp[0][1-(str[0]-'0')] = 1;
    for (int i = 1; i < n; i++) {
        if (str[i]-'0') {
            dp[i][0] = dp[i-1][1] + 1 + pow(2, i) - 1;
            dp[i][1] = dp[i-1][0];
        }
        else {
            dp[i][1] = dp[i-1][1] + 1 + pow(2, i) - 1;
            dp[i][0] = dp[i-1][0];
        }
    }
    cout << dp[n-1][0] << endl;
    return 0;
}